백준 22352번
https://www.acmicpc.net/problem/22352

문제

---

생각하기

---

• BFS를 통해서 문제를 해결 하였다.

• 크게 어려운 문제는 아닌데 생각보다 많이 헤맸다...

동작

        boolean flag = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!flag && before[i][j] != after[i][j]) {
                    BFS(i, j, before[i][j], after[i][j]);
                    flag = true;
                }
            }
            if(flag) break;
        }

BFS()는 before와 after의 처음으로 달라지는 부분에서 한번만 실행하면 된다.

매개변수로 일치하지 않는 부분의 before의 숫자 값과, after의 숫자 값을 가지고 간다.

        before[x][y] = colorA;
        visited[x][y] = true;
        que.offer(new Coordinate(x, y));

        while (!que.isEmpty()) {
            Coordinate current = que.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = current.x + dirX[i];
                int nextY = current.y + dirY[i];

                if (ableCheck(nextX, nextY, visited, colorB)) {
                    que.offer(new Coordinate(nextX, nextY));
                    visited[nextX][nextY] = true;
                    before[nextX][nextY] = colorA;
                }
            }
        }

여기서 before에 after의 색상을 입히는데 기존의 before 색상과 같은 값들만 바꾸도록 해준다.

이렇게 만들어진 before배열과 after배열을 비교했을 때 다른 값이 없는 경우에 정답이 된다.

결과

코드

---

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[][] before, after;
    private static final int[] dirX = {0, 0, -1, 1};
    private static final int[] dirY = {-1, 1, 0, 0};

    private static class Coordinate {
        int x;
        int y;

        private Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    } // End of Coordiante class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();
        bw.write(solve());

        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        boolean flag = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!flag && before[i][j] != after[i][j]) {
                    BFS(i, j, before[i][j], after[i][j]);
                    flag = true;
                }
            }
            if(flag) break;
        }


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (before[i][j] != after[i][j]) {
                    sb.append("NO");
                    return sb.toString();
                }
            }
        }


        sb.append("YES");
        return sb.toString();
    } // End of solve()

    private static void BFS(int x, int y, int colorB, int colorA) {
        LinkedList<Coordinate> que = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];

        before[x][y] = colorA;
        visited[x][y] = true;
        que.offer(new Coordinate(x, y));

        while (!que.isEmpty()) {
            Coordinate current = que.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = current.x + dirX[i];
                int nextY = current.y + dirY[i];

                if (ableCheck(nextX, nextY, visited, colorB)) {
                    que.offer(new Coordinate(nextX, nextY));
                    visited[nextX][nextY] = true;
                    before[nextX][nextY] = colorA;
                }
            }
        }
    } // End of BFS()

    private static boolean ableCheck(int nextX, int nextY, boolean[][] visited, int colorB) {
        return nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && !visited[nextX][nextY] && before[nextX][nextY] == colorB;
    } // End of ableCheck()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        before = new int[N][M];
        after = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                before[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                after[i][j] = Integer.parseInt(st.nextToken());
            }
        }

    } // End of input()
} // End of Main class