[BOJ] 18352 특정 거리의 도시 찾기 - JAVA

1. 문제

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

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

---

2. 풀이

Node 클래스

인접리스트를 위한 클래스를 만들었다. 도시번호, 그 다음 이어진 도시의 링크를 저장한다.

private static class Node {
   int num;
   Node link;
   Node(int num, Node link){
      this.num = num;
      this.link = link;
   }
}

 

입력부분

1.  도시 번호가 1부터 시작하기때문에 N+1 크기의 Node 배열을 만든다. 이름은 head로 했다. 

2.  방향이 있는 그래프이므로 from, to를 구분해서 넣는다. head[from]위치에 현재 head[from]을 링크로 하는 새로운 Node 객체를 생성해 저장한다. 예제1의 head[1]을 예시로 든다면 이런 식이다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.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());

Node[] head = new Node[N+1];

int from,to;
for(int i=0;i<M;i++){
   st = new StringTokenizer(in.readLine());
   from = Integer.parseInt(st.nextToken());
   to = Integer.parseInt(st.nextToken());
   head[from] = new Node(to,head[from]);
}

 

BFS

1.  int[]를 담는 queue를 만들어서 BFS탐색을 진행한다. 0번째 칸에는 도시 번호, 1번째 칸에는 거리 길이를 저장했다.

2.  이 때, 인접리스트이므로 for문을 이용하되 시작은 link=head[now[0], link가 null이 되기 전까지 link = link.link로 바꿔가면서 반복한다. 이 반복문 전에 head[now[0]]==null인 경우를 걸렀다.

3.  now[1]이 K인 경우에는 list에 담고 다음 Node를 탐색하지 않으려고 continue를 시켰다. BFS는 depth 순서로 탐색을 하기 때문이다.

boolean[] visited = new boolean[N+1];
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{X,0});

int[] now;
visited[X] = true;
ArrayList<Integer> list = new ArrayList<>();
while(!queue.isEmpty()){
   now = queue.poll();
   if(now[1]==K){
      list.add(now[0]);
      continue;
   }

   if(head[now[0]]==null) continue;

   for(Node link = head[now[0]];link != null;link = link.link){
      if(visited[link.num]) continue;
      queue.offer(new int[]{link.num,now[1]+1});
      visited[link.num] = true;
   }
}

 

출력

1.  만약 list의 size가 0이라면 해당 도시가 없으므로 -1을 출력하고 끝낸다.

2.  list를 오름차순으로 정렬한다.

3.  StringBuilder 객체를 생성한 뒤 list원소를 하나하나 담고 한 번에 출력한다.

if(list.size()==0){
   System.out.println(-1);
   return;
}

Collections.sort(list);
StringBuilder sb = new StringBuilder();
for(int i=0;i<list.size();i++){
   sb.append(list.get(i)).append('\n');
}
System.out.print(sb);

---

3. 결과

. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 범위를 고려하지 않고 인접행렬로 틀렸다가 메모리초과가 났다.