[백준] 18352 : 특정 거리의 도시 찾기 - JAVA

문제분석

모든 도로의 거리가 1이므로 가중치가 없는 연결리스트로 이 그래프를 표현할 수 있다.
도시개수의 최대가 300,000 도로 개수의 최대가 1,000,000이므로 BFS탐색을 수행하면 시간 복잡도 안에서 해결할 수 있다.

BFS의 시간복잡도 = O(V+E)

또한 일정한 거리에대해 모든 노드를 찾는것이므로 BFS가 DFS보다 빠를것이다.

Troubleshooting

public class Main {
static int[] visited;
static ArrayList<Integer>[] city;
static List<Integer> answer;
	public static void main(String[] args) throws IOException {
		answer = new ArrayList<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
		boolean twoExist = false;
		city = new ArrayList[N+1];
		visited = new int[N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			city[A].add(B);	//에러 발생 지점 	
		}
		BFS(X);
		for(int i=1; i<N+1; i++) {
			if(visited[i] == 2) {
				System.out.println(i);
				twoExist = true;
			}
		}
		if(!twoExist) System.out.println("-1");
	}
	private static void BFS(int node) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(node);
		while(!queue.isEmpty()) {
			int now_node = queue.poll();
			for(int i : city[now_node]) {
				if(visited[i] == 0) {
					queue.add(i);
					visited[i] = visited[now_node]++;
				}
			}
			if(visited[now_node]++ == 3) { //Troubleshooting 2 원인
				break;
			}
		}
	}
}

문제

NullPointerException 에러가 났다.

원인

city가 초기화 되어있지않을 상태에서 사용했다.

해결

for(int i=1; i<N+1; i++) {
		city[i] = new ArrayList<>();
}

city를 초기화했다.

Troubleshooting 2

문제

예제 1에서 4가 출력되어야하는데, 2,3이 출력됐다.

원인

if(visited[now_node]++ == 3) 에서 조건문에 false여도 visited[now_node]++는 정상적으로 수행되었기때문에 문제가 발생한것이다.

해결

if(visited[now_node]++ == 3) -> if(visited[now_node]+1 == 3) 수정

Troubleshooting 3

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

public class Main {
static int[] visited;
static ArrayList<Integer>[] city;
static List<Integer> answer;
static int K;
	public static void main(String[] args) throws IOException {
		answer = new ArrayList<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
		boolean kExist = false;
		city = new ArrayList[N+1];
		visited = new int[N+1];
		for(int i=1; i<N+1; i++) {
			city[i] = new ArrayList<>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			city[A].add(B);		
		}
		BFS(X);
		for(int i=1; i<N+1; i++) {
			if(visited[i] ==K) {
				System.out.println(i);
				kExist = true;
			}
		}
		if(!kExist) System.out.println("-1");
	}
	private static void BFS(int node) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(node);
		while(!queue.isEmpty()) {
			int now_node = queue.poll();
			for(int i : city[now_node]) {
				if(visited[i] == 0) {
					queue.add(i);
					visited[i] = visited[now_node]+1;
				}
			}
			if(visited[now_node]+1 == K+1) {
				break;
			}
		}
	}
}

문제

예제는 다 맞았는데, 틀렸습니다를 받았다.

원인

단방향 화살표가 한 도로에서 각각 2개있는경우(즉, 양방향 그래프와 동일한 효과를 주면)를 생각하지 못했다. A -> B -> A

꼭 그것이아니더라도 A -> B -> C -> A 처럼 다시 출발 노드로 돌아올 수 있는데,이 경우를 방지하기위해 출발노드도 방문했다고 체크가 필요하다.

하지만 나는 출발노드에 다시 돌아올일이 없다고 생각해서 visited를 0으로 초기화했음에도 처음 출발노드에 거리를 0으로 그대로 두었다.

해결

visited를 -1로 초기화하고, 처음 출발노드는 거리를 0으로 업데이트했다.

제출코드

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

public class Main {
static int[] visited;
static ArrayList<Integer>[] city;
static List<Integer> answer;
static int K;
	public static void main(String[] args) throws IOException {
		answer = new ArrayList<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
		boolean kExist = false;
		city = new ArrayList[N+1];
		visited = new int[N+1];
		for(int i=0 ;i<N+1; i++) {
			visited[i] = -1;
		}
		for(int i=1; i<N+1; i++) {
			city[i] = new ArrayList<>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			city[A].add(B);		
		}
		visited[X] =0;
		BFS(X);
		for(int i=1; i<N+1; i++) {
			if(visited[i] ==K) {
				System.out.println(i);
				kExist = true;
			}
		}
		if(!kExist) System.out.println("-1");
	}
	private static void BFS(int node) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(node);
		while(!queue.isEmpty()) {
			int now_node = queue.poll();
			for(int i : city[now_node]) {
				if(visited[i] == -1) {
					queue.add(i);
					visited[i] = visited[now_node]+1;
				}
			}
			if(visited[now_node]+1 == K+1) {
				break;
			}
		}
	}
}

공부한 사항

• BFS 코드 로직
• Queue 선언법
• ArrayList[] 선언법