[구름톤 챌린지 19일차] 대체 경로

문제를 요약하자면 i번째엔 그래프의 i번 노드를 통과하지 못하고 목적지까지 도달할 수 있는지, 도달할 수 있다면 최소 몇개의 노드를 통과해서 갈수 있는지 알아내는 것이다. 이번 문제는 연결 리스트로 그래프를 구현하여 해결하였다.

 

배운 점

목적지에 최단 횟수로 도달하는 방법을 알아내려면 dfs보단 bfs가 더 나은거 같단 생각이 들었다. dfs는 어떤 한 길을 택하고 그 길이 목적지에 도달할 수 있는지 없는지 알아낸다면 bfs는 모든 길에 동등한 차수를 우선적으로 방문하기 때문이다. 물론 이럼에도 중복해서 노드를 방문할 가능성이 있기 때문에 이런 점을 counting이란 배열을 선언해서 각 노드에 해당하는 counting 배열의 위치에 최단거리를 저장하는 식으로 풀었다.

느낀 점

여전히 코드를 테스트할 때마다 문법적 오류와 논리적 오류를 겪고 시작한다. 언제쯤 이런 루틴에서 벗어날 수 있을지... 한번에 테스트를 통과하는 그 날이 기다려진다.

어려웠던 점

디버깅 할때를 제외하곤 특별히 어려웠던 점은 없었다.

import java.io.*;
import java.util.*;
class Main {
	static List<Integer>[] graph; 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] NMSE = br.readLine().split(" ");
		int N = Integer.parseInt(NMSE[0]);
		int M = Integer.parseInt(NMSE[1]);
		int S = Integer.parseInt(NMSE[2]);
		int E = Integer.parseInt(NMSE[3]);
		
		graph = new ArrayList[N + 1];
		for (int i = 0; i <= N; i++) {
      graph[i] = new ArrayList<>();
    }

		
		for(int i = 0; i < M; i++){
			String[] ab = br.readLine().split(" ");
			int a = Integer.parseInt(ab[0]);
			int b = Integer.parseInt(ab[1]);
			graph[a].add(b);
			graph[b].add(a);
		}
		
		bfs(S, E, N);
	}
	
	public static void bfs(int start, int end, int N){			
		for(int i = 1; i <= N; i++){
			int [] counting = new int [N + 1];
			Arrays.fill(counting, 9999);
			Queue<Integer> q = new LinkedList<>();
			boolean visited[] = new boolean[N + 1];
			int banned = i;
			if(banned == start || banned == end){
				System.out.println(-1);
				continue;
			}
			q.add(start);
			counting[start] = 1;
			while(!q.isEmpty()){
				int node = q.poll();
				if(node == banned) continue;
				if(visited[node] == true) continue;						
				visited[node] = true;
				if(node == end) {
					break;
				}
		
				for(int j = 0; j < graph[node].size(); j++){
					int temp = graph[node].get(j);
					if(visited[temp] == true) continue;
					counting[temp] = (counting[node] + 1 < counting[temp]) ? counting[node] + 1 : counting[temp];
					q.add(temp);
					
				}				
			}//while문 끝
			if(visited[end] != true) System.out.println(-1);
			else System.out.println(counting[end]);
		} //for문 끝
	}//bfs 함수 끝
}//class Main 끝