G1976. 여행가자

문제

제출 코드

• 사용 알고리즘 : bfs

• 원래 union을 사용하여 푸는 문제이지만, bfs를 사용하여 풀었다
• 첫번째 노드부터 순서대로 bfs를 시작해서, 시작노드를 방문체크 배열(visit)에 적어주었다
• 계속 문제가 틀려서 헤맸는데, 디버깅 과정에서 출력값을 더 적은것을 지우지 않아 그랬다

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class G1976_trip {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());

		List<Integer>[] edge = new List[N+1];
		for(int i=1; i<=N; i++) {
			edge[i] = new ArrayList<Integer>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				if(st.nextToken().equals("1")) edge[i].add(j);
			}
		}

		int[] visit = new int[N+1];
		for(int i=1; i<=N; i++) {
			if(visit[i]!=0) continue;
			Queue<Integer> queue = new LinkedList<Integer>();
			queue.add(i);
			visit[i] = i;
			while(!queue.isEmpty()) {
				int now = queue.poll();
				for(int node: edge[now]) {
					if(visit[node]!=0) continue;
					queue.add(node);
					visit[node] = i;
				}
			}
		}

		String[] str = br.readLine().split(" ");
		int parent = visit[Integer.parseInt(str[0])];
		for(String s : str) {
			if(parent != visit[Integer.parseInt(s)]) {
				parent = -1;
				break;
			}
		}

		System.out.println((parent==-1 || parent==0) ? "NO" : "YES");
	}

}