[BOJ] 14466.소가 길을 건너간 이유 6(DFS, BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

처음에 문제를 잘못 이해하고 이상하게 접근했었다..

그래서~ 문제를 잘 이해했는지 재정의하는게 중요헌 것이다~!

(근데 사실 테케도 하나라서.. 핑계..)

생각보다(?) 간단하게

소 한 마리씩 길을 건너지 않고 이동할 수 있는 모든 곳을 이리저리 다녀본다.

그 후! 해당 소가 이동하지 않은 곳에 소가 있는지 확인하고

있다면? 길을 건너지 않으면 만나지 못 하는 상황에 놓인 소 한 쌍이 된다.

어떻게 보면 평범한 DFS, BFS 완탐 문제인데,

길을 어떻게 관리할지가 포인트인 것 같다.

특정 좌표는 여러 좌표와 길이 연결될 수 있다.

그래서 좌표마다 여러 좌표를 저장할 수 있는 공간이 필요하다.

여러 방법이 있겠지만,

나는 각 좌표가 여러 정보를 가질 수 있는

2차원 list를 선택했다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BOJ14466 {       static int N, K, R;     static boolean[][] visited;     static Point[] cows;     static ArrayList<Point>[][] bridges;     static int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};          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()); // 크기         K = Integer.parseInt(st.nextToken()); // 소 몇 마리?         R = Integer.parseInt(st.nextToken()); // 길           cows = new Point[K];         bridges = new ArrayList[N][N];         for (int i = 0; i < N; i++) {             for (int j = 0; j < N; j++) {                 bridges[i][j] = new ArrayList<>();             }         }                  // 다리 정보 저장         for (int i = 0; i < R; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken()) - 1;             int b = Integer.parseInt(st.nextToken()) - 1;             int c = Integer.parseInt(st.nextToken()) - 1;             int d = Integer.parseInt(st.nextToken()) - 1;                          bridges[a][b].add(new Point(c, d));             bridges[c][d].add(new Point(a, b));         }                  // 소 위치 저장         for (int i = 0; i < K; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken()) - 1;             int b = Integer.parseInt(st.nextToken()) - 1;                          cows[i] = new Point(a, b);         }                  System.out.println(go());     }       private static int go() {                  int cnt = 0;                  // 소 한 마리씩 길을 건너지 않고 이동해보자.         for (int c = 0; c < K; c++) {             visited = new boolean[N][N];             move(cows[c].x, cows[c].y);                           for (int nc = c; nc < K; nc++) {                 Point cow = cows[nc];                 // 이 소가 방문하지 않은 곳에 소가 있다면                 // 길을 건너지 않으면 만나지 못 하는 쌍이 된다.                 if(!visited[cow.x][cow.y]) cnt++;             }           }                          return cnt;     }       private static void move(int x, int y) {                  visited[x][y] = true;                  for (int d = 0; d < 4; d++) {             int xx = x + dx[d];             int yy = y + dy[d];             // 범위             if(xx < 0 || xx >= N || yy < 0 || yy >= N) continue;             // 이미 방문             if(visited[xx][yy]) continue;             // 길을 건너야 한다면             if(bridges[x][y].contains(new Point(xx, yy))) continue;                          move(xx, yy);         }              }   }   Colored by Color Scripter

cs

line 61) 소 한 마리씩 길을 건너지 않고 이동

line 70) 해당 소가 방문하지 않은 곳에 다른 소가 있다면 cnt++