[백준] 16197. 두 동전 (Java)

 

16197번: 두 동전

풀이

혼자 일부러 더럽고 어렵게 푼 느낌? 🙄 암튼 오래걸림

• 문제에 나온 그대로 시뮬레이션 문제 풀듯 풀었다.
• 짜잘짜잘한 조건들이 많아서 테케 넣어보고 수정하고 하다보니 푸는데 오래걸렸다..

---

고민거리와 삽질의 흔적들

두 동전은 어떻게 동시에 움직이지?

• 일차원 배열을 생성해서 반복문으로 변수 값을 할당했다.
• 0<= d <=3 반목문 안에 0 <= i < 2 반복문을 넣어서 두 개를 동시에 빼서 진행하면 된다.

떨어진 상태를 어떻게 확인하지?

• 처음에 동전이 떨어지면 큐에 넣지 않았음
  • 그럼 이제 두 쌍 중 한 쌍만 남는다.
  • 큐에서 두 쌍을 뽑았을 때 두 쌍의 거리 정보가 다르면 동전이 떨어진 뜻이겠지?!
  • 라고 생각했으나 그렇게 단순하게 되지 않았다 (예시 테케 넣어보니 틀림)
• 떨어진 동전도 큐에 넣되 거리 정보를 갖고 있도록 하자
  • 떨어진 동전은 아예 d = -1로 해놓고 처음에 조건에서 걸러지도록 하니 되었다.

visited check는 어떻게?

• 처음에 단순 해당 위치 방문 횟수로 하려 함
• 그러면 벽에서 머무르는 횟수나 아무튼 중간에 꼬임
• 해결법은 범위가 <=20이므로 String값으로 만들어서 HashMap으로 방문체크함

---

코드

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

public class Main {
    static int N, M;
    static int[] px = {1, 0, -1, 0};
    static int[] py = {0, 1, 0, -1};
    static char[][] map;
    static Queue<Coin> coin = new LinkedList<>();

    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 = new char[N][M];

        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();

            for (int j = 0; j < M; j++)
                if (map[i][j] == 'o') coin.add(new Coin(i, j, 0));
        }

        explore();
        br.close();
    }

    public static void explore() {
        // visited check: 두 동전이 계속 같은 위치에 머무를 때
        Map<String, Boolean> visited = new HashMap<>();
        while (!coin.isEmpty()) {
            int[] x = new int[2];
            int[] y = new int[2];
            int[] cnt = new int[2];
            int[] dir = new int[2];

            for (int i = 0; i < 2; i++) {
                x[i] = coin.peek().x;
                y[i] = coin.peek().y;
                cnt[i] = coin.peek().cnt;
                dir[i] = coin.peek().d;
                coin.poll();
            }

            if (dir[0] != dir[1]) {
                if (cnt[0] <= 10) System.out.println(cnt[0]);
                else System.out.println(-1);

                return;
            }
            else {
                if (dir[0] == -1) continue;
                if (cnt[0] > 10) {
                    System.out.println(-1);
                    return;
                }
            }

            for (int d = 0; d < 4; d++) {
                StringBuilder sb = new StringBuilder();
                sb.append(x[0] + px[d]).append(y[0] + py[d]).append(x[1] + px[d]).append(y[1] + py[d]);
                if (visited.get(sb.toString()) != null) continue;
                visited.put(sb.toString(), true);

                for (int i = 0; i < 2; i++) {
                    int nx = x[i] + px[d];
                    int ny = y[i] + py[d];

                    if (!isIn(nx, ny)) {
//                        System.out.println("동전 탈출, " + x[i] + ", " + y[i] + "| d, cnt: " + d + ", " + (cnt[i] + 1));
                        coin.offer(new Coin(x[i], y[i], (cnt[i] + 1), -1));
                    }
                    else if (map[nx][ny] == '#') {
//                        System.out.println("벽 만남, " + x[i] + ", " + y[i] + "| d, cnt: " + d + ", " + (cnt[i] + 1));
                        coin.offer(new Coin(x[i], y[i], (cnt[i] + 1), d));
                    }
                    else {
//                        System.out.println("빈칸 or 동전 겹침, " + x[i] + ", " + y[i] + "| d, cnt: " + d + ", " + (cnt[i] + 1));
                        coin.offer(new Coin(nx, ny, (cnt[i] + 1), d));
                    }
                }
            }
        }
        System.out.println(-1);
    }

    public static boolean isIn(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M) return false;
        return true;
    }

    static class Coin {
        int x;
        int y;
        int cnt;
        int d;

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

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

}