[백준/자바] 1976번: 여행 가자

문제

https://www.acmicpc.net/problem/1976

풀이

• 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다.
• 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자.
• 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오.

여행 경로 중 모든 지점에 대해 연결된 경로가 있는 지 살피는 문제입니다.
이는 주로 Union-Find나 Floyd-Warshall 알고리즘으로 해결할 수 있습니다.
2가지 모두 사용해 풀어봤습니다.

Union-Find

유니온 파인드 알고리즘을 사용할 때는 앞서 부모 배열과 사이즈 배열을 선언해 주어야 합니다.

	private static void make() {
		p = new int[n+1];
		s = new int[n+1];
		for (int i = 1; i <= n; i++) {
			p[i] = i;
			s[i] = 1;
		}
	}

• 부모, 사이즈 배열을 초기화할 때에는 부모는 자기 자신을 가리키고 사이즈 배열은 집합 안에 본인 혼자만 존재하므로 1로 설정해 주어야 합니다.

		graph = new int[n+1][n+1];
		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
        // 여행 경로
		StringTokenizer st = new StringTokenizer(br.readLine());
		cmd = new int[m];
		for (int i = 0; i < m; i++) {
			cmd[i] = Integer.parseInt(st.nextToken());
		}

• 후엔 모든 입력을 받아 저장해 줍니다.

	private static void setRoot() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][j] == 1) union(i, j);
			}
		}
	}

• 이제 경로를 탐색하기 위해 이동할 수 있는 모든 경로를 압축해 줍니다.
• 만약 i -> j 경로가 존재한다면, 이를 하나의 집합으로 묶어 줍니다.

	private static boolean union(int a, int b) {
		int ra = find(a);
		int rb = find(b);
		
		if (ra == rb) return false;
		
		if (s[ra] < s[rb]) {
			int t = ra;
			ra = rb;
			rb = t;
		}
		
		p[rb] = ra;
		s[ra] += s[rb];
		return true;
	}

• a의 부모와 b의 부모를 갖고 와 합집합 연산을 시작합니다.
• 만약 이미 a와 b의 부모가 같다면(같은 집합에 속해 있다면) 연산을 진행하지 않고 return
• 사이즈 기반으로 집합을 합칠 것이니, 만약 ra의 크기가 rb보다 작다면 둘을 swap
• 후에 rb를 ra의 밑으로 넣어 줍니다.

	private static int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}

• 부모를 찾는 find() 메서드입니다.
• 만약 부모가 자기 자신일 경우에는 자신을 return
• 아니라면 부모 x의 부모를 찾는 연산을 하여 경로를 압축해 줍니다.

	private static void getAnswer() {
		int root = find(cmd[0]);
		for (int i = 1; i < m; i++) {
			if (find(cmd[i]) != root) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}

• 이제 시작점과 모든 여행 경로의 부모를 비교하여 만약 같지 않다면 같은 집합이 아니므로(길이 이어져 있지 않으므로) NO를 출력하고 끝냅니다.
• 모든 부모를 비교해 같은 집합이라면 YES를 출력해 줍니다.

Floyd-Warshall

코드 자체는 플로이드 워셜이 훨씬 간결합니다.
대신 플로이드 워셜 알고리즘은 시간 복잡도가 O(N^3)이라 최악의 경우 시간 초과가 발생할 수 있습니다.
그러나 이번 문제에서는 N과 M의 크기가 매우 작으므로 충분히 해결 가능한 시간입니다.

입력은 위와 똑같이 받아 주는데, 한 가지 조건만 추가하면 됩니다.

if (i == j) graph[i][j] = 1;

• 그래프 입력 시, 자기 자신의 위치일 경우 1로 만들어 줍니다.
• 이는 만약 자기 자신의 위치에서 자신의 위치로 도달이 가능하다는 것을 의미합니다.

	private static void floyd() {
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (graph[i][k] == 1 && graph[k][j] == 1) {
						graph[i][j] = 1;
					}
				}
			}
		}
	}

• 입력을 마치면, 바로 경로 압축이 시작 됩니다.
• i -> k 경로가 존재하고 k -> j 경로가 존재한다면, i -> j가 존재하는 것이므로 i -> j 경로도 길이 있다고 표현해 주면 됩니다.

	private static void getAnswer() {
		for (int i = 0; i < m - 1; i++) {
			if (graph[cmd[i]][cmd[i+1]] == 0) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}

• 그리고 여행 경로를 차례대로 모든 좌표를 비교하며, 길이 없다면 NO를 출력하고 끝내 주면 됩니다.
• 반복문이 종료되면, 모든 경로가 길이 존재한다는 것이므로 YES를 출력하면 끝입니다.

코드

Union-Find

import java.util.*;
import java.io.*;

public class Main_1976 {
	static int n, m;
	static int[] cmd;
	static int[][] graph;
	
	static int[] p, s;
	
	private static void make() {
		p = new int[n+1];
		s = new int[n+1];
		for (int i = 1; i <= n; i++) {
			p[i] = i;
			s[i] = 1;
		}
	}
	
	private static int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}
	
	private static boolean union(int a, int b) {
		int ra = find(a);
		int rb = find(b);
		
		if (ra == rb) return false;
		
		if (s[ra] < s[rb]) {
			int t = ra;
			ra = rb;
			rb = t;
		}
		
		p[rb] = ra;
		s[ra] += s[rb];
		return true;
	}
	
	private static void setRoot() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][j] == 1) union(i, j);
			}
		}
	}
	
	private static void getAnswer() {
		int root = find(cmd[0]);
		for (int i = 1; i < m; i++) {
			if (find(cmd[i]) != root) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		graph = new int[n+1][n+1];
		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		cmd = new int[m];
		for (int i = 0; i < m; i++) {
			cmd[i] = Integer.parseInt(st.nextToken());
		}
		
		make();
		setRoot();
		getAnswer();
	}

}

Floyd-Warshall

import java.io.*;
import java.util.*;

public class Main {
	static int n, m;
	static int[] cmd;
	static int[][] graph;
	
	private static void floyd() {
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (graph[i][k] == 1 && graph[k][j] == 1) {
						graph[i][j] = 1;
					}
				}
			}
		}
	}
	
	private static void getAnswer() {
		for (int i = 0; i < m - 1; i++) {
			if (graph[cmd[i]][cmd[i+1]] == 0) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = Integer.parseInt(br.readLine());
    	m = Integer.parseInt(br.readLine());
    	
    	graph = new int[n+1][n+1];
    	for (int i = 1; i <= n; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for (int j = 1; j <= n; j++) {
    			graph[i][j] = Integer.parseInt(st.nextToken());
    			if (i == j) graph[i][j] = 1;
    		}
    	}
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	cmd = new int[m];
    	for (int i = 0; i < m; i++) {
    		cmd[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	floyd();
    	getAnswer();
    }
}