아이디어

• 그래프는 인접행렬로 받는다.
• 모든 도시에 대해 연결된 도시끼리 분리집합(union-find)를 형성하자.
• 여행 계획에서, 인접한 두 점끼리 같은 집합에 있으면 해당 두 도시 사이에는 경로가 있다는 뜻이다.
• 중간에 경로가 끊기는 도시가 있다면 "NO", 아니면 "YES"다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, M;
	static boolean[][] graph;
	static int[] path;
	
	static int[] parent;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		M = Integer.parseInt(rd.readLine());
		
		graph = new boolean[N+1][N+1];
		for (int i=1; i<=N; i++) {
			tk = new StringTokenizer(rd.readLine());
			for (int j=1; j<=N; j++) {
				graph[i][j] = tk.nextToken().charAt(0) == '1';
			}
		}
		
		path = new int[M];
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<M; i++)
			path[i] = Integer.parseInt(tk.nextToken());
		
		makeSet();
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				if (graph[i][j])
					union(i, j);
			}
		}
		
		for (int i=0; i<M-1; i++) {
			if (findSet(path[i]) != findSet(path[i+1])) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}
	
	static void makeSet() {
		parent = new int[N+1];
		for (int i=1; i<=N; i++)
			parent[i] = i;
	}
	
	static int findSet(int x) {
		if (parent[x] == x) return x;
		return parent[x] = findSet(parent[x]);
	}
	
	static void union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		if (px == py) return;
		parent[py] = px;
	}
}

메모리 및 시간

• 메모리: 48508 KB
• 시간: 412 ms

리뷰

• 입력을 받는 방식이 특이해서 주의해야 하는 문제
  • 처음에 tk.tokenCount() > 1인지로 판단했다가, 시간초과가 났었다.
• 위에서 말했던 거처럼 2차원 동적 테이블 2개를 번갈아가며 사용하는 형태로 바꾼다면 메모리를 크게 줄일 수 있을 것이다.
• 내 풀이에서는 상향식으로 했는데, 하향식 코드(재귀)를 쓰는 게 오히려 시간이 줄어들 것 같다.