[백준] 14466. 소가 길을 건너간 이유 6

문제 링크

[백준] 14466. 소가 길을 건너간 이유 6

풀이 과정

문제의 예시 입력을 그림으로 나타내면 위와 같습니다.

1. 1번 소 → 2번 소

1번 소는 길을 이용해야지만 2번 소가 있는 위치로 이동할 수 있습니다. 가능한 두 점 사이의 경로는 위 두 가지 말고도 여러 개가 존재하지만, 결국 길을 사용해야만 한다는 점을 알 수 있습니다.

2. 1번 소 → 3번 소

1번 소는 길을 이용해야지만 3번 소가 있는 위치로 갈 수 있습니다. 위의 경우와 마찬가지로 여러 경로가 존재하지만, 결국 길을 사용해야만 합니다.

3. 2번 소 → 3번 소

2번 소는 길을 이용하지 않고 3번 소의 위치로 이동할 수 있습니다. 위에 나타난 경로는 길을 사용하지 않고 갈 수 있는 경로들 중 하나를 보여줍니다.

문제 풀이에는 일반적인 bfs 탐색 알고리즘을 사용했습니다. 그래프를 상하좌우 방향으로 탐색하면서 소를 찾아가되, 길을 사용하게 되는 경로는 택하지 않는 방법으로 문제를 풀었습니다.

List<Integer>[] adj = new ArrayList[N * N + 1];
for (int i = 1; i < adj.length; i++) {
    adj[i] = new ArrayList<>();
}

for (int i = 0; i < R; i++) {
    int from = convert(sc.nextInt(), sc.nextInt());
    int to = convert(sc.nextInt(), sc.nextInt());

    adj[from].add(to);
    adj[to].add(from);
}

문제에서 주어진 길에 대한 정보는 인접 리스트로 구현했으며, 배열의 인덱스 값을 사용하기 위해 모든 2차원 좌표값을 1차원으로 변환 후 사용했습니다.

static int convert(int x, int y) {
    return (x - 1) * N + y;
}

다음은 2차원의 좌표 값을 1차원의 인덱스로 변환하는 convert 메소드입니다. 각각의 좌표는 위 식에 따라 아래와 같이 1 ~ N*N 의 인덱스를 갖게 됩니다.

for (int i = 0; i < K - 1; i++) {
    for (int j = i + 1; j < K; j++) {
        Point from = new Point(k[i].x, k[i].y);
        Point to = new Point(k[j].x, k[j].y);

        bfs(from, to);
    }
}

이후 가능한 모든 쌍에 대해 bfs 탐색을 시작합니다.

if (now.x == dest.x && now.y == dest.y) {
    reachWithoutRoad = true;
    break;
}

if (!reachWithoutRoad) {
    answer++;
}

현재 큐에서 제거한 요소가 목적지 좌표와 일치하는 경우, 문제에서 주어진 길을 사용하지 않고도 목적지까지 갈 수 있는 경로가 존재함을 의미하고, 이를 boolean 변수 reachWithoutRoad 에 기록해둡니다. 만약 bfs 탐색이 모두 끝날때까지 해당 값이 false 이면, 길을 건너지 않으면 갈 수가 없다는 것을 의미하고, 답을 위해 카운트 해줍니다.

코드

import java.awt.*;
import java.util.*;
import java.util.List;

public class Main {
    static int N, K, R;
    static Point[] k;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static List<Integer>[] adj;
    static boolean[] visit;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();
        R = sc.nextInt();

        adj = new ArrayList[N * N + 1];
        for (int i = 1; i < adj.length; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < R; i++) {
            int from = convert(sc.nextInt(), sc.nextInt());
            int to = convert(sc.nextInt(), sc.nextInt());

            adj[from].add(to);
            adj[to].add(from);
        }

        k = new Point[K];
        for (int i = 0; i < K; i++) {
            k[i] = new Point(sc.nextInt(), sc.nextInt());
        }

        for (int i = 0; i < K - 1; i++) {
            for (int j = i + 1; j < K; j++) {
                Point from = new Point(k[i].x, k[i].y);
                Point to = new Point(k[j].x, k[j].y);

                bfs(from, to);
            }
        }

        System.out.println(answer);
    }

    static void bfs(Point start, Point dest) {
        Queue<Point> queue = new LinkedList<>();
        visit = new boolean[N * N + 1];

        queue.add(start);
        visit[convert(start.x, start.y)] = true;

        boolean reachWithoutRoad = false;

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            if (now.x == dest.x && now.y == dest.y) {
                reachWithoutRoad = true;
                break;
            }

            for (int d = 0; d < 4; d++) {
                int next_i = now.x + di[d];
                int next_j = now.y + dj[d];

                int from = convert(now.x, now.y);
                int to = convert(next_i, next_j);

                if (next_i < 1 || next_i > N || next_j < 1 || next_j > N || visit[convert(next_i, next_j)] || adj[from].contains(to))
                    continue;

                queue.add(new Point(next_i, next_j));
                visit[convert(next_i, next_j)] = true;
            }
        }

        if (!reachWithoutRoad) {
            answer++;
        }
    }

    static int convert(int x, int y) {
        return (x - 1) * N + y;
    }
}