[BOJ] 1325번 효율적인 해킹 (Java)

백준 1235 효율적인 해킹

DFS와 BFS 두 방법 모두 가능한 문제지만 BFS로 풀었다. ArrayList 배열을 선언했고, 메모리 초과를 방지하기 위해 인접 리스트로 풀었다. DFS와 BFS를 활용할 때는 언제나 DP도 같이 사용할 수 있는지 확인한다. 1가지 문제로 인해서 DP를 활용하기 힘들었다.

방문한 노드는 계산에서 빼기 때문에, 노드가 겹친 경우 DP로 값을 저장하면 오차가 생길 수 있다.

또한 ArrayList 배열를 초기화하는 방법과 update하는 방식이 중요했다. 또한 BFS 함수를 만들 때, 작은 실수 때문에 시간초과가 났고 실수를 찾기까지 오래 걸렸다.

		public static int correct_bfs(int x) {
        Queue <Integer> dq = new LinkedList<>();
        int tmp;
        int cnt = 0;
        dq.add(x);
        isVisit[x] = 1;
        while (!dq.isEmpty()) {
            tmp = dq.poll();
            for (int c : table[tmp]) {
                if (isVisit[c] == 0) {
                    dq.add(c);
  // 이 부분 바로 업데이트 하지 않으면 필요 이상의 반복을 하게 된다.
                    isVisit[c] = 1;	
                    cnt++;
                }
            }
        }
        return cnt;
    }

  public static int incorrect_bfs(int x) {
        Queue <Integer> dq = new LinkedList<>();
        int tmp;
        int cnt = 0;
        dq.add(x);
        while (!dq.isEmpty()) {
            tmp = dq.poll();
  // 이 부분 바로 업데이트 하지 않아서 필요 이상의 반복을 하게 된다.
            isVisit[tmp] = 1;
            cnt++;
            for (int c : table[tmp]) {
                if (isVisit[c] == 0) {
                    dq.add(c);
                }
            }
        }
        return cnt;
    }

정답 코드

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


class Main{

  public static int bfs(int x) {
      Queue <Integer> dq = new LinkedList<>();
      int tmp;
      int cnt = 0;
      dq.add(x);
      while (!dq.isEmpty()) {
          tmp = dq.poll();
          isVisit[tmp] = 1;
          cnt++;
          for (int c : table[tmp]) {
              if (isVisit[c] == 0) {
                  dq.add(c);
              }
          }
      }
      return cnt;
  }


  static int [] isVisit;
  static ArrayList<Integer> table[];
  public static void main(String[] args) {
      try {
          int n, m, s, e;
          int []dp;
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
          n = Integer.parseInt(st.nextToken());
          m = Integer.parseInt(st.nextToken());
          table = new ArrayList [n + 1] ;
          dp = new int[n + 1];
			// ArrayList 배열 초기화
          for (int i = 1; i <= n; i++) {
              table[i] = new ArrayList<>();
          }
          while (m-- > 0) {
              st = new StringTokenizer(br.readLine());
              s = Integer.parseInt(st.nextToken());
              e = Integer.parseInt(st.nextToken());
              table[e].add(s);	// 배열 속 ArrayList update
          }
          int maxV = 0;
          for (int i = 1; i <= n; i++) {
              isVisit = new int [n + 1];
              dp[i] = bfs(i);
              maxV = Math.max(maxV, dp[i]);
          }
          for (int i = 1; i <= n; i++) {
              if(dp[i] == maxV){
                  System.out.printf("%d ", i);
              }
          }
      } catch (Exception e) {
          e.printStackTrace();
      }
  }
}