백준 18352번 자바

1. 문제

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

2. 접근 방식

처음 접근을 dfs로 했으나 문제에서 주어진 최단거리 K보다 짦은 거리의 노드 관계를 해결하지 못해 포기했다. 사실 '틀렸습니다'가 종종 시간초과를 포함하는 경우가 있어서 정확히 잘못된 부분은 모르겠다. 아마 시간 초과일 확률이 클듯하다..

public static void dfs(int node, int distance) {
		visited[node]++;
		if (visited[node] >= 1 && result.contains(node) && distance < K) {
			result.remove(Integer.valueOf(node));
		}
		if (distance == K) {
			result.add(node);
			return;
		}
		
		for (int i=0; i<city[node].size(); i++) {
			int next = city[node].get(i);
			dfs(next, distance + 1);
		}
	}

결국 bfs로 접근을 바꿨고 bfs여서 K보다 짦은거리의 노드관계에 대한 부분을 굳이 구현할 필요가 없었다. 

다른 탐색 문제는 방문배열로 주로 boolean타입을 사용했는데 여기선 int를 사용해 방문횟수 == 거리가 되도록 설정했다. 

 

3. 구현

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

public class Main18352 {

	static int N,M,K,X;
	static int[] visited;
	static List<Integer>[] city;
	static List<Integer> result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		city = new ArrayList[N+1];
		result = new ArrayList<Integer>();
		visited = new int[N+1];
		for (int i=1; i<=N; i++) {
			city[i] = new ArrayList<Integer>();
		}
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			city[start].add(end);
		}
		for (int i=0; i<=N; i++) {
			visited[i] = -1;
		}
		bfs(X);
		for (int i=0; i<=N; i++) {
			if (visited[i] == K) {
				result.add(i);
			}
		}
		if (result.isEmpty()) {
			System.out.println(-1);
		}
		Collections.sort(result);
		for (Integer ans : result) {
			System.out.println(ans);				
		}
	}
	
	public static void bfs(int node) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(node);
		visited[node]++;
		while (!q.isEmpty()) {
			int now = q.poll();
			for (int i=0; i<city[now].size(); i++) {
				if (visited[city[now].get(i)] == -1) {
					visited[city[now].get(i)] = visited[now] + 1;
					q.add(city[now].get(i));
				}
			}
		}
	}
}

4. 정리

시간날 때 dfs로 풀 수 있는 방법은 없는지 다시 한번 살펴보자