[백준] BOJ 16197 두 동전 (골드 4)

문제

---

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

16197: 두 동전

---

풀이

---

1. DFS를 통해 갈 수 있는 모든 경로를 이동해본다
2. 이때, depth가 10이상이라면 더 이상 탐색하지 않는다.
3. 4방향 중 한 방향으로 두 동전을 이동 시키는 move함수를 정의한다.
   해당 함수는 아래와 같은 로직을 수행한다.
   1. 만약 이동한 위치가 범위 밖이라면 null 리턴
   2. 만약 이동한 위치가 벽이라면 원래 위치 그대로 리턴
   3. 둘 다 아니라면 이동한 위치 리턴
4. 위의 과정을 두 동전 모두 수행하고 결과를 이용하여 가능한지 판단한다.
   1. 둘 중 하나만 null인 경우 (1개만 나간 경우) -> 끝! (최소와 비교해서 갱신)
   2. 둘 다 나가지 않은 경우 -> 계속 탐색
   3. 둘 다 null인 경우 (둘 다 밖으로 나간 경우) -> 더 이상 진행 X
5. 초기에 시작할 때 flag = false로 설정하고 한번이라도 가능한 경우가 나오면
   flag = true로 설정하고 최소 횟수를 출력하고 아니면 -1을 출력

---

코드 (DFS)

---

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

public class BOJ16197 {
    static char[][] board;
    static Coin[] coins = new Coin[2];
    static int N, M, min = Integer.MAX_VALUE;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static boolean flag;
    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());

        int idx = 0;
        board = new char[N][M];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = input.charAt(j);
                if (board[i][j] == 'o') {
                    coins[idx++] = new Coin(i, j);
                }
            }
        }
        dfs(coins[0], coins[1], 1);
        System.out.println(flag ? min : -1);
    }

    public static void dfs(Coin coin1, Coin coin2, int depth) {
        if(depth > 10) return;

        for (int i = 0; i < 4; i++) {
            Coin nCoin1 = move(coin1.x, coin1.y, i);
            Coin nCoin2 = move( coin2.x, coin2.y, i);

            if (nCoin1 == null && nCoin2 == null) continue;
            if (nCoin1 == null || nCoin2 == null) {
                min = Math.min(min, depth);
                flag = true;
                return;
            }
            dfs(nCoin1, nCoin2, depth + 1);
        }
    }

    public static Coin move(int x, int y, int delta) {
        int nx = x + dx[delta];
        int ny = y + dy[delta];

        if (!isValid(nx, ny)) return null;
        if (board[nx][ny] == '#') return new Coin(x, y);
        return new Coin(nx, ny);
    }
    public static boolean isValid(int x, int y){
        if (x < 0 || y < 0 || x >= N || y >= M) return false;
        return true;
    }
}

class Coin{
    int x, y;

    public Coin(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

---

결론

---

 

다른 스터디원들의 풀이를 보니 [x1][y1][x2][y2]로 두 동전의 상태를 관리하는

4차원 visit 배열을 사용하여 BFS를 수행하는 것을 알게되었다!. 

해당 방법을 사용하면 BFS의 특성 상 가중치 없는 최단 문제로 풀리게 되어 DFS보다 효율적일 것이다!.

4차원 배열을 이런식으로 사용하는 방법을 생각해내지 못했지만, 다른 스터디원들 덕에 또 하나 배울 수 있었다!.

---