백준 국기 색칠하기(30702)

 

오늘의 문제는  DFS문제로 풀어봤다.

 

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

30702번: 국기 색칠하기

 

문제는 A국기를 B국기를 만들 수 있냐는 질문이었다.

 

해당 문제 풀이에 대해서 고민을 해본 결과 하나의 해답을 정했다.

 

 

풀이

메모리 제한이 굉장히 너프한 것을 보면 힌트를 얻을 수 있을 수 도 있다.

 

하나의 색으로 이루어 진 부분을 part라고 지칭하겠다. 

 

문제는 A의 part가 B에 국기에 대조했을때 B국기에 해당 part의 색이 모두 똑같으면 된다.

 

만약 하나라도 틀리게되면 국기를 바꿀 수 없는것이다.

 

3 6
AABBCC
AABBCC
AABBCC
DDEEFF
DDEEFF
DDEEFF

 

예를 들어 위에  예제에서는

 

AA
AA
AA 

 

BB
BB
BB

 

CC
CC
CC

 

위 3영역의 위치가 B도 동일하게 같은지 확인하면된다.

 

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 String[][] A, B;
    static int N, M;
    static boolean[][] visited;

    static int[][] dir = {
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
    };

    public static void main(String[] args) throws IOException {
        solution();
    }


    public static void solution() 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());

        A = new String[N][M];
        B = new String[N][M];
        visited = new boolean[N][M];

        for (int i=0; i < N; i++) {
            String[] str = br.readLine().split("");
            for (int j=0; j < M; j++) {
                A[i][j] = str[j];
            }
        }

        for (int i=0; i < N; i++) {
            String[] str = br.readLine().split("");
            for (int j=0; j < M; j++) {
                B[i][j] = str[j];
            }
        }

        for (int i=0 ; i < N; i++) {
            for (int j=0; j < M; j++) {
                if (!visited[i][j]) {
                    Queue<int[]> queue = new LinkedList<>();
                    dfs(i, j, A[i][j], queue);
                    if (!check(queue)) {
                        System.out.println("NO");
                        return;
                    }
                }
            }
        }

        System.out.println("YES");
    }

    public static void dfs(int x, int y, String target, Queue<int[]> queue) {
        visited[x][y] = true;
        queue.add(new int[]{x, y});

        for (int i=0; i < dir.length; i++) {
            int x1 = x + dir[i][0];
            int y1 = y + dir[i][1];

            if (x1>=0 && y1 >=0 && x1 < N && y1 < M && !visited[x1][y1] && target.equals(A[x1][y1])) {
                dfs(x1, y1, target, queue);
            }

        }

    }


    public static boolean check(Queue<int[]> queue) {
        int[] num = queue.poll();
        int x = num[0];
        int y = num[1];
        String target = B[x][y];

        while (!queue.isEmpty()) {

            num = queue.poll();
            x = num[0];
            y = num[1];
            String s = B[x][y];

            if (!target.equals(s)) {
                return false;
            }

        }

        return true;
    }
}

 

결과