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을 큐의 초기값으로 넣어준다.

큐에 값이 남아있을 경우 아래 과정을 반복한다.

1. 큐의 첫번째 요소를 start에 담아준다.
2. visited[start]는 방문했다고 체크(true)한다.
3. 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 안의 과정은 아래와 같다.

1. 만약 매개변수로 받은 s의 길이가 만들어야 하는 길이 len과 같다면 s를 return한다.
2. 그렇지 않으면 s에 차례대로 1, 2, 3을 붙이며 인접한 두 부분 수열이 일치하지 않는 경우를 찾는다. (isSatisfied 호출)
3. isSatisfied의 값이 true라면 다시 DFS를 호출한다.
4. 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;
     }
}