[BOJ] 16197. 두 동전

[작성일]

• 2022-02-22

[분류]

• bfs
  
  
  

[문제링크]

• https://www.acmicpc.net/problem/16197
  
  
  

[요구사항]

• 동전이 한 개만 떨어질 때까지 최소 횟수를 구하라.
  
  
  

[풀이]

최소 횟수라는 말을 보고 바로 bfs를 떠올렸다. 큐에 조건에 맞는 동전의 좌표쌍을 넣고 빼는 것을 반복하면서 한 개만 밖으로 나갈 경우 해당 cnt를 출력해주는 식으로 구현하였다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};
    static int N, M;
    static char[][] map;
    static boolean[][][][] visited;
    static int sx1, sy1, sx2, sy2;

    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());
        M = Integer.parseInt(st.nextToken());

        // map 입력받기
        int count = 0;
        map = new char[N][M];
        visited = new boolean[N][M][N][M];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'o') {
                    if (count == 0) {
                        sx1 = i;
                        sy1 = j;
                        count++;
                    } else if (count == 1) {
                        sx2 = i;
                        sy2 = j;
                    }
                }
            }
        }

        System.out.println(bfs(sx1, sy1, sx2, sy2, 0));
    }

    public static int bfs(int x1, int y1, int x2, int y2, int cnt) {
        Queue<Move> q = new LinkedList<>();
        q.add(new Move(x1, y1, x2, y2, cnt));
        visited[x1][y1][x2][y2] = true;

        while (!q.isEmpty()) {
            Move now = q.poll();
            if (now.cnt == 10) continue;

            for (int i = 0; i < 4; i++) {
                int nx1 = now.x1 + dx[i];
                int ny1 = now.y1 + dy[i];
                int nx2 = now.x2 + dx[i];
                int ny2 = now.y2 + dy[i];

                // 바깥으로 하나만 나가는 경우
                if ((isBorder(nx1, ny1) && !isBorder(nx2, ny2))
                        || (!isBorder(nx1, ny1) && isBorder(nx2, ny2))) {
                    return now.cnt + 1;
                }

                // 조건에 맞는 경우 큐에 추가 - 1.방문X, 2.둘다 map범위밖X, 3.벽인 경우 보정
                if (!isBorder(nx1, ny1) && !isBorder(nx2, ny2)) {
                    if (map[nx1][ny1] == '#') {
                        nx1 = now.x1;
                        ny1 = now.y1;
                    }
                    if (map[nx2][ny2] == '#') {
                        nx2 = now.x2;
                        ny2 = now.y2;
                    }

                    if (!visited[nx1][ny1][nx2][ny2]) {
                        visited[nx1][ny1][nx2][ny2] = true;
                        q.add(new Move(nx1, ny1, nx2, ny2, now.cnt + 1));
                    }
                }
            }
        }
        return -1;
    }

    public static boolean isBorder(int x, int y) {
        return (x < 0 || y < 0 || x > N - 1 || y > M - 1);
    }
}

class Move {
    int x1;
    int y1;
    int x2;
    int y2;
    int cnt;

    public Move(int x1, int y1, int x2, int y2, int cnt) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.cnt = cnt;
    }
}

[느낀점]

bfs도 조건만 잘 잡고 구현하면 크게 오래 걸리지 않는 것 같다.