Graph, DFS, BFS 연습문제 - 인접 행렬, 바코드
1. 인접 행렬 생성하기
문제
방향이 있는 간선과 방향이 없는 간선들의 목록들을 받아 2차원 배열의 인접행렬을 반환하는 함수를 작성하세요.
조건
각 간선은 3가지 정보를 담고 있습니다.
- 0번째: 간선의 시작 정점 (0 이상의 정수)
- 1번째: 간선의 도착 정점 (0 이상의 정수)
- 2번째: 방향성 (1 == 일시 무향, 0 == 일시 방향)
입력
인자 1: edges
- int 타입의 방향/무향인 간선들의 목록이 담긴 배열
출력
- Array 타입을 리턴해야 합니다.
- 2차원 배열의 인접 행렬
주의 사항
- 정점 0에서 정점 4로 이어주는 간선이 존재할 경우 정점 1, 2, 3도 존재합니다.
- 반환하는 인접행렬은 2차원 배열이며, 행(row)는 바깥 배열, 열(column)은 안쪽 배열입니다.
- int[][] matrix = new int[][]{{0, 0}, {0, 0}}
- matrix[0] == 0번째 행
- matrix[0][0] == 0번째 행의 0번째 열
- 두 정점간의 간선의 유무는 0과 1로 표시합니다.
- 0: 두 정점간에 간선이 존재하지 않을 경우
- 1: 두 정점간에 간선이 존재할 경우
- 아래의 2차원 배열에서 세로축은 시작 정점, 가로축은 도착 정점입니다.
- 음수는 올 수 없습니다.
- 입력된 배열 edges는 수정하지 말아야 합니다.
- self loop 없습니다.
풀이
문제에서 말하는 무향, 방향이 헷갈렸는데 쉽게 얘기하면 1일 경우 Start → End, End → Start 모두 길이 있고, 0일 경우는 Start → End로만 갈 수 있다.
입력으로 주어진 이차원 배열 edges는 {Start, End, direction}로 이루어져 있다.
우선 edges의 Start, End 값들 중 최댓값을 찾고 그 값보다 1만큼 큰 이차원 배열 result를 만들어준다. (간선의 유무를 표시하고 반환해줄 배열)
입력으로 받은 Start, End는 Direction의 값에 상관 없이 Start → End 간선은 존재하기 때문에 result[Start][End]에 1을 넣어준다.
그리고 만약 Direction == 1 이라면 result[End][Start]의 값도 1을 넣어준다.
정답
package com.codestates.coplit;
import java.util.*;
public class Solution {
public int[][] createMatrix(int[][] edges) {
int max = 0;
for(int[] i : edges) {
if(i[0]>max) max = i[0];
if(i[1]>max) max = i[1];
}
int[][] result = new int[max+1][max+1];
for(int[] i : edges) {
int start = i[0];
int end = i[1];
int direction = i[2];
result[start][end] = 1;
if(direction == 1) result[end][start] = 1;
}
return result;
}
}2. 인접 행렬 길찾기
문제
주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다.
입력
인자 1: matrix
- Array 타입을 요소로 갖는 인접 행렬이 담긴 2차원 배열
인자 2: from
- int 타입의 시작 정점
인자 3: to
- int 타입의 도착 정점
출력
- boolean 타입을 리턴해야 합니다.
주의사항
- 입력된 배열 matrix을 수정하지 말아야 합니다.
풀이
size : 정점의 수
queue : 다음 방문할 곳들을 저장할 큐
visited : 방문한 적이 있는지 체크할 배열
먼저 from을 큐의 초기값으로 넣어준다.
큐에 값이 남아있을 경우 아래 과정을 반복한다.
- 큐의 첫번째 요소를 start에 담아준다.
- visited[start]는 방문했다고 체크(true)한다.
- start에서 갈 수 있는 길이 있으면서 방문한 적이 없는 정점을 큐에 넣어준다.
만약 큐가 비어있을 때 visited[to]가 true라면 이어지는 길이 존재한다고 판단하고 true를 반환한다.
정답
package com.codestates.coplit;
import java.util.*;
public class Solution {
public boolean getDirections(int[][] matrix, int from, int to) {
int size = matrix.length;
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[size];
queue.add(from);
while(!queue.isEmpty()) {
int start = queue.poll();
visited[start] = true;
for(int i=0; i<size; i++) {
if(matrix[start][i]==1&&visited[i]==false) {
queue.add(i);
}
}
}
return visited[to]==true ? true : false;
}
}3. 연결된 정점들
문제
방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.
입력
인자 1: edges
- 2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록 (2차원 배열, 정수 요소)
- ex) [[0, 1], [1, 2], [3, 4]]
출력
- int 타입을 리턴해야 합니다.
- 연결된 정점의 컴포넌트의 수를 숫자로 반환합니다.
주의 사항
- 입력된 배열 edges는 수정하지 말아야 합니다.
- 주어진 간선은 무향입니다.
- [1, 2] 는 정점 1에서 정점 2로도 갈 수 있으며, 정점 2에서 정점 1로도 갈 수 있습니다.
풀이
2번 문제와 유사하게 풀었지만 다른 점이 있다면 이어진 길이 끝날 때 count 변수의 값을 +1 해주는 것이다.
만약 1-2-5-6의 경로로 반복문이 한 번 끝나고 3-4의 경로로 끝났다면 count 변수의 값은 2가 된다.
정답
package com.codestates.coplit;
import java.util.*;
public class Solution {
public int connectedVertices(int[][] edges) {
int max = 0;
for(int[] i : edges) {
if(i[0]>max) max = i[0];
if(i[1]>max) max = i[1];
}
int[][] newArray = new int[max+1][max+1];
for(int[] i : edges) {
newArray[i[0]][i[1]] = 1;
newArray[i[1]][i[0]] = 1;
}
boolean visit[] = new boolean[max+1];
Queue<Integer> queue = new LinkedList<>();
int count = 0;
for(int i=0; i<max+1; i++) {
if(visit[i]==false) {
queue.add(i);
while(!queue.isEmpty()) {
int start = queue.poll();
for(int k=0; k<max+1; k++) {
if(newArray[start][k]==1&&visit[k]==false) {
visit[k]=true;
queue.add(k);
}
}
}
count++;
}
}
return count;
}
}4. 바코드
문제
1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 무조건 1, 2, 3만 붙여서 바코드를 만들었다면 쉬웠겠지만, 아쉽게도 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.
만들 수 없는 바코드 만들 수 있는 바코드
| 112 | 1312 |
| 1231312 | 3 |
| 232312 | 231213 |
- 부분 수열? 주어진 수열에서 연속된 모든 구간을 말합니다. 수열 123의 부분 수열은 1, 2, 3, 12, 23, 123 입니다.
- 인접한 두 부분 수열? 첫번째 부분 수열과 두번째 부분 수열이 연속된 경우를 말합니다.
- 수열 1234에서 인접한 부분 수열 (우리는 두 부분수열이 같은지 관심이 있으므로 길이가 서로 다른 경우는 무시한다)
- 1과 2, 2와 3, 3과 4, 12와 34입니다.
- 만들 수 없는 바코드를 보자면,
- '11'2
- 12'3131'2
- '2323'12 인접한 두 개의 부분 수열이 동일하기 때문에 만들 수 없습니다. 고로, '12131213'과 같이 네 자리씩 중복되어도 만들 수 없습니다. 자릿수와 상관없이, 인접한(붙어있는) 부분 수열이 같다면 바코드를 만들 수 없습니다.
입력
인자 1: len
- int 타입의 1 이상 50 이하의 자연수
출력
- String 타입을 리턴해야 합니다.
- 예시로, 121도, 123도 전부 바코드로 제작할 수 있지만 제일 작은 수는 121이기 때문에 121을 반환해야 합니다.
풀이
어떤 수든지 최소값을 만들려면 가장 앞에는 “1”이 들어와야 한다.
그리고 뒤에 값들은 1, 2, 3을 차례대로 넣으며 들어갈 수 있는 값을 찾는 게 중요하다.
“1” → “11” (X) ”1” → “12” (O)
“12” → “121” (O)
“121” → “1211” (X)
“121” → “1212” (X)
“121” → “1213” (O)
초기값으로 1을 넣어주고 재귀함수 DFS를 호출한다.
DFS 안의 과정은 아래와 같다.
- 만약 매개변수로 받은 s의 길이가 만들어야 하는 길이 len과 같다면 s를 return한다.
- 그렇지 않으면 s에 차례대로 1, 2, 3을 붙이며 인접한 두 부분 수열이 일치하지 않는 경우를 찾는다. (isSatisfied 호출)
- isSatisfied의 값이 true라면 다시 DFS를 호출한다.
- 1, 2, 3이 모두 들어갈 수 없는 수로 판단되면 null을 return한다.
isSatisfied 메서드에서 값을 비교할 때는 s 길이의 절반까지만 보면 된다.
예를 들어 s = “12345678” 이고 값을 뒤에 하나씩 넣으며 판단한다고 생각해보자.
s+i 에서 i가 1일 때 비교 과정은 다음과 같다. ( s = “123456781” )
1==8 → 81==67 → 781==456 → 6781==2345
그 이상은 인접한 부분 수열이 존재하지 않는다.
따라서 위 과정으로 비교하다가 같은 부분이 발견되면 해당 숫자는 뒤에 올 수 없기 때문에 false를 return하면 된다.
정답
package com.codestates.coplit;
import java.util.*;
public class Solution {
public String barcode(int len) {
return DFS("1", len);
}
static String DFS(String s, int len) {
if(s.length()==len) return s;
for(int i=1; i<=3; i++) {
String newStr = s+i;
if(isSatisfied(newStr)) {
String result = DFS(newStr, len);
if (result != null) return result;
}
}
return null;
}
static boolean isSatisfied(String s) {
int len = s.length();
for(int i=1; i<=s.length(); i++) {
if(len >= i*2 && s.substring(len-(i*2), len-i).equals(s.substring(len-i, len))) {
return false;
}
}
return true;
}
}