[백준/java] 1976. 여행 가자

문제 링크 - https://www.acmicpc.net/problem/1976

🌱 문제

🌱 풀이

• 문제에서 요구하는 것은 여행 계획에 속한 도시들이 주어졌을 때, 여행이 가능한지만 판별하면 되는 문제였다.
• 그렇기 때문에 계획으로 주어진 도시들이 연결된 그래프이면 YES이고, 하나라도 연결되어 있지 않으면 NO를 출력하면 되는 꽤 간단한 문제라는 생각이 들었다.
• 그래서 내가 주어진 모든 도시들에 대해서 BFS를 돌렸고, 인접한 도시들과 union&find 를 통해서 조상을 일치시켜 주었다.
• 모든 도시들에 대해 BFS를 마친 후, 여행경로로 주어진 도시들을 탐색하면서 하나라도 조상이 다른 도시가 있다면, 연결되어있지 않은 것이므로 (= 여행할 수 없는 것이므로) NO를 출력하도록 해주었다.

개선할 점

• 아래 부분의 코드를 보면 나는 모든 도시에 대해서, 각 도시가 방문체크 되지 않았다면 전부 BFS를 도는 과정을 하고 있다.
• 또한 인접한 도시를 찾는 과정도 행렬을 탐색하면서 일일이 찾기 때문에 꽤나 비효율적이었다.

	for(int i=1; i<=N; i++) { // 모든 도시에 대해서 연결된 도시들 살펴보기 
			if(visit[i]==false) { // 이미 살펴본 도시면 패스 
				Queue<Integer> queue = new LinkedList<Integer>();
				visit[i]=true;
				queue.add(i);
				while(!queue.isEmpty()) {
					int cur = queue.poll();
					for(int j=1; j<=N; j++) { // 행렬을 통해 cur도시와 인접한 도시 찾는 과정 
						if(arr[cur][j]==1 && visit[j]==false) {
							if(getParent(cur)!=getParent(j)) {
								union(cur,j);
								visit[j]=true;
								queue.add(j);
								
							}
						}
					}
				}
			}
		}

• 문제를 풀고나서 내 풀이가 맞는지 궁금해서 구글링을 해보았다.
• 모든 도시에 대해서 BFS를 돌지 않고, 단순히 행렬에서 값을 1로 가지는 행과 열에 대해서 union&find 연산을 해주면 좀더 효율적으로 연결된 도시들을 확인할 수 있었다.!

	// 연결된 도시에 한해서 union & find 연산 진행 
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(arr[i][j]==1 && parent[i]!=parent[j])
					union(i,j);
			}
		}

🌱 코드 (BFS)

package _2023.Jan_week01;

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

// 1976. 여행 가자 
public class boj_1976 {
	static int N, M;
	static int arr[][];
	static int travel[]; // 여행경로 저장하는 배열 
	static boolean visit[]; // 연결된 도시 살펴볼때, 이미 살펴봤는지를 확인하는 배열 
	static int parent[]; // 조상 저장하는 배열 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N=Integer.parseInt(br.readLine());
		M=Integer.parseInt(br.readLine());
		
		arr =new int[N+1][N+1];
		travel = new int[M];
		visit = new boolean[N+1];
		parent = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			parent[i]=i;
			st= new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			travel[i]=Integer.parseInt(st.nextToken());
		}
		
		for(int i=1; i<=N; i++) { // 모든 도시에 대해서 연결된 도시들 살펴보기 
			if(visit[i]==false) { // 이미 살펴본 도시면 패스 
				Queue<Integer> queue = new LinkedList<Integer>();
				visit[i]=true;
				queue.add(i);
				while(!queue.isEmpty()) {
					int cur = queue.poll();
					for(int j=1; j<=N; j++) {
						if(arr[cur][j]==1 && visit[j]==false) {
							if(getParent(cur)!=getParent(j)) {
								union(cur,j);
								visit[j]=true;
								queue.add(j);
								
							}
						}
					}
				}
			}
		}
		
		boolean flag = true;
		for(int i=0; i<M-1; i++) {
			//여행 경로에 속한 도시중에 하나라도 이어지지 않은 도시가 있으면 정답은 NO가 되므로 그 이후로는 살펴볼 필요 없음 
			if(getParent(travel[i])!=getParent(travel[i+1])) {
				flag=false;
				break;
			}
			
		}
		if(flag==true)
			System.out.println("YES");
		else
			System.out.println("NO");
		
	
	}
	public static int getParent(int x) {
		if(parent[x]==x)
			return x;
		return parent[x]=getParent(parent[x]);
	}
	
	public static void union(int x, int y) {
		x=getParent(x);
		y=getParent(y);
		if(x>y)
			parent[x]=y;
		else
			parent[y]=x;
	}

}

🌱 수정한 코드

package _2023.Jan_week01;

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

// 1976. 여행 가자 
public class boj_1976 {
	static int N, M;
	static int arr[][];
	static int travel[]; // 여행경로 저장하는 배열 
	static boolean visit[]; // 연결된 도시 살펴볼때, 이미 살펴봤는지를 확인하는 배열 
	static int parent[]; // 조상 저장하는 배열 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N=Integer.parseInt(br.readLine());
		M=Integer.parseInt(br.readLine());
		
		arr =new int[N+1][N+1];
		travel = new int[M];
		visit = new boolean[N+1];
		parent = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			parent[i]=i;
			st= new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			travel[i]=Integer.parseInt(st.nextToken());
		}
		
		// 연결된 도시에 한해서 union & find 연산 진행 
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(arr[i][j]==1 && parent[i]!=parent[j])
					union(i,j);
			}
		}
		
		boolean flag = true;
		for(int i=0; i<M-1; i++) {
			//여행 경로에 속한 도시중에 하나라도 이어지지 않은 도시가 있으면 정답은 NO가 되므로 그 이후로는 살펴볼 필요 없음 
			if(getParent(travel[i])!=getParent(travel[i+1])) {
				flag=false;
				break;
			}
			
		}
		if(flag==true)
			System.out.println("YES");
		else
			System.out.println("NO");
		
	
	}
	public static int getParent(int x) {
		if(parent[x]==x)
			return x;
		return parent[x]=getParent(parent[x]);
	}
	
	public static void union(int x, int y) {
		x=getParent(x);
		y=getParent(y);
		if(x>y)
			parent[x]=y;
		else
			parent[y]=x;
	}

}