99클럽 코테 스터디 11일차 TIL (미들러): [백준][Java] 25195 Yes or yes - 골드4

 

문제 보기

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

 

 

풀이

미들러에 골드 4 문제가 나와서 의아하겠으나 충분히 쉽게 풀 수 있는 문제이다.

 

나도 풀이를 생각해 낸 뒤 바로 한 번에 해결하였다.

 

우선 팬클럽이 있는 곳은 갈 필요가 없는 노드라고 생각 해도 된다.

그래서 난 visited 배열에 true로 체크하였다.

 

  while(true) {
    int cur = q.poll();
    if(graph[cur].isEmpty()) {
      bw.write("yes\n");
      break;
    }
    for(int i = 0; i < graph[cur].size(); i++) {
      if(!visited[graph[cur].get(i)]) {
        visited[graph[cur].get(i)] = true;
        q.add(graph[cur].get(i));
      }
    }

    if(q.isEmpty()) {
      bw.write("Yes\n");
      break;
    }
  }

그리고 yes인지 Yes인지 출력할 부분이다.

문제에서는 특정 노드까지 이동 하는 것이 아니라, 간선이 끊겼을 경우가 마지막 노드라고 말했다.

그러므로 graph에 다음 노드가 없을 경우 yes를 출력하도록 했다.

 

중요한 점은 visited에서 걸러질 경우(팬클럽이 있을 경우) 큐에 담지 않기 때문에 다음 반복까지 갈 수 없다.

그래서 다음 간선들을 탐색했음에도 불구하고 큐가 비어있을 경우에는 Yes를 출력하도록 했다.

 

그리고 하나 중요한 점이 있다.

이 방식을 사용할 경우 첫 번째 노드에 팬클럽이 있을 경우를 거를 수 없다.

if(visited[1]) {
  bw.write("Yes\n");
}

그러니 미리 예외 처리를 해 두자.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    List<Integer>[] graph = new List[N + 1];
    for(int i = 1; i <= N; i++) {
      graph[i] = new ArrayList<>();
    }
    while(M-- > 0) {
      st = new StringTokenizer(br.readLine());
      graph[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
    }

    int S = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine());
    boolean[] visited = new boolean[N + 1];
    while(S-- > 0) {
      visited[Integer.parseInt(st.nextToken())] = true;
    }

    if(visited[1]) {
      bw.write("Yes\n");
    } else {
      Queue<Integer> q = new LinkedList<>();
      q.add(1);
      while(true) {
        int cur = q.poll();
        if(graph[cur].isEmpty()) {
          bw.write("yes\n");
          break;
        }
        for(int i = 0; i < graph[cur].size(); i++) {
          if(!visited[graph[cur].get(i)]) {
            visited[graph[cur].get(i)] = true;
            q.add(graph[cur].get(i));
          }
        }

        if(q.isEmpty()) {
          bw.write("Yes\n");
          break;
        }
      }
    }

    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/25195.%E2%80%85Yes%E2%80%85or%E2%80%85yes

CodingTest_AutoSave/백준/Gold/25195. Yes or yes at main · MetroDefro/CodingTest_AutoSave