16197 - 두 동전

생각했던 것

문제의 모양을 보고 바로 BFS 문제라고 생각했다. 다만, 생각없이 visited 처리를 넣는 바람에 시간이 많이 걸렸다.
문제의 키 포인트는 "벽에대한 처리"와, xor를 이용한 "동전이 하나만 떨어졌을 때의 감지"이다.

추가적으로, 최소해를 찾기 위해서는 각 순회마다 따로 count를 세어줘야한다. (재귀를 사용한다면, 메소드의 파라미터에 count를 넘겨주므로 신경쓰지 않아도 됨)

나는 bfs를 반복문으로 구현했기 때문에, 각 순회마다 따로 count를 세어주었다.

++ 예전에 풀었던 7576 - 토마토 문제에서는, count를 기록해주는 배열을 따로 만들어두었다. 해당 문제에서는 벽이 없었기 때문에, 해당 방식으로 저장 할 수 있었던것 같다.

실수

4방향 BFS에서 visited는 당연히 필요없다. visited가 있다면, 다음 순회로 넘어갈 때 이미 이전 순회에서 true를 4개나 만들어 두었으므로, 다음 순회를 정상적으로 진행 할 수 없게 된다.

아쉬운 점

코드에서 볼 수 있듯이, 동전이 2개이므로 순회마다 동전 2개의 위치를 저장한다. 해당 구현 방식에서 순회 횟수인 count를 두 동전에 모두 저장하는데, 실제로 사용하는 값은 두 개 중 하나만 사용한다. 같은 클래스를 사용하다보니 이렇게 되었는데.. 더 최적화 할 방법이 있을지도?

내 코드의 장점

해당 문제에서 원하는 답의 경우는 "두 개의 동전 중 하나의 동전만 떨어졌을 때"인데, 각각의 동전이 떨어진 상태를 boolean 변수에 넣어두고 xor 연산을 이용해 하나만 떨어졌을 때를 감지했다. 가독성도, 효율성도 이 방식이 가장 좋은듯하다.

package backjoon;

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

class P_16197{
    static class Cord {
        int x;
        int y;
        int count;
        Cord(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static String[][] map;

    public static int bfs(ArrayList<Cord> coins) {
        Queue<Cord> fir = new LinkedList<>();
        Queue<Cord> sec = new LinkedList<>();
        fir.add(coins.get(0));
        sec.add(coins.get(1));
        while (!fir.isEmpty() && !sec.isEmpty())
        { // 남 북 동 서
            Cord first = fir.poll();
            Cord second = sec.poll();
            int fx = first.x;
            int fy = first.y;
            int sx = second.x;
            int sy = second.y;
            if (first.count >= 10) break;
            for (int i = 0; i < 4; i++) {
                int fnx = fx + dx[i];
                int fny = fy + dy[i];
                int snx = sx + dx[i];
                int sny = sy + dy[i];
                boolean in_f = (fnx >= 0 && fnx < map.length && fny >= 0 && fny < map[0].length);
                boolean in_s = (snx >= 0 && snx < map.length && sny >= 0 && sny < map[0].length);
                if (in_f ^ in_s) return (first.count + 1);
                else { // 0 0, 1 1
                    if (in_f) // 1 1
                    {
                        if (map[fnx][fny].equals("#") && !map[snx][sny].equals("#")) {
                            fir.add(new Cord(fx, fy, first.count + 1));
                            sec.add(new Cord(snx, sny, second.count + 1));
                        } else if (!map[fnx][fny].equals("#") && map[snx][sny].equals("#")) {
                            sec.add(new Cord(sx, sy, first.count + 1));
                            fir.add(new Cord(fnx, fny, second.count + 1));
                        } else if (!map[fnx][fny].equals("#") && !map[snx][sny].equals("#")) {
                            fir.add(new Cord(fnx, fny, first.count + 1));
                            sec.add(new Cord(snx, sny, second.count + 1));
                        }
                    }
                }
            }
        }
        return (-1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        map = new String[N][M];
        ArrayList<Cord> coins = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String[] elem = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = elem[j];
                if (map[i][j].equals("o")) coins.add(new Cord(i, j, 0));
            }
        }
        System.out.println(bfs(coins));
    }
}