[알고리즘 / 백준] 10026 - 적록색약

www.acmicpc.net/problem/10026

10026번: 적록색약

 

문제는 위와 같으며, DFS 방식을 통해 같은 색으로 연관된 구역을 찾아 그 수를 세는 방식으로 문제를 해결하였습니다. 적록색약인 경우와 아닌 경우가 있으므로, DFS 를 두번 처리하는 방식으로 문제를 해결하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 적록색약이 아닌 경우 같은 색으로 칠해진 구역 확인하기
def dfs(x, y):
    need_visit = [[x, y]]
    visited[x][y] = True

    while need_visit:
        cx, cy = need_visit.pop()

		# 상하좌우로 연관된 다음 위치를 확인하여
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]

            if 0 <= nx < n and 0 <= ny < n:
                if grid[cx][cy] == grid[nx][ny] and not visited[nx][ny]:  # 같은 색으로 칠해져 있지만 아직 확인하지 않은 경우
                    need_visit.append([nx, ny])  # 확인해야하는 구역으로 추가하고
                    visited[nx][ny] = True  # 확인한 것으로 처리


# 적록색약인 경우 같은 색으로 칠해진 구역 확인하기
def blindness_dfs(x, y):
    need_visit = [[x, y]]
    blindness_visited[x][y] = True

    while need_visit:
        cx, cy = need_visit.pop()

		# 상하좌우로 연관된 다음 위치를 확인하여
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]

            if 0 <= nx < n and 0 <= ny < n:
            	# 같은 색으로 칠해져있거나 현재 위치가 R 이고 다음 위치가 G 인 경우 또는 현재 위치가 G 이고 다음 위치가 R 이면서 아직 확인하지 않은 경우
                if (grid[cx][cy] == grid[nx][ny] or (grid[cx][cy] == 'R' and grid[nx][ny] == 'G')
                    or (grid[cx][cy] == 'G' and grid[nx][ny] == 'R')) and not blindness_visited[nx][ny]:
                    need_visit.append([nx, ny])  # 확인해야 하는 구역으로 추가하고
                    blindness_visited[nx][ny] = True  # 확인한 것으로 처리


n = int(stdin.readline())
grid = []
for _ in range(n):
    grid.append(stdin.readline().strip())

visited = [[False] * n for _ in range(n)]  # 적록색맹이 아닌 경우 방문한 구역인지 확인할 배열
blindness_visited = [[False] * n for _ in range(n)]  # 적록색맹인 경우 방문한 구역인지 확인할 배열
count = [0, 0]  # [적록색맹이 아닌 사람이 본 구역 수, 적록색맹인 사람이 본 구역 수] 저장

# 그리드의 모든 위치를 확인하면서
for i in range(n):
    for j in range(n):
        if not visited[i][j]:  # 적록색맹이 아닌 사람이 보는 구역 확인
            dfs(i, j)
            count[0] += 1  # 적록색맹이 아닌 사람이 본 구역 수 추가

        if not blindness_visited[i][j]:  # 적록색맹인 사람이 보는 구역 수 확인
            blindness_dfs(i, j)
            count[1] += 1  # 적록색맹인 사람이 본 구역 수 추가

print(count[0], count[1])

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    private static int n;
    private static String[] grid;

    private static boolean[][] visited;
    private static boolean[][] blindness_visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        grid = new String[n];
        for (int i = 0; i < n; i++) {
            grid[i] = br.readLine();
        }

        visited = new boolean[n][n];
        blindness_visited = new boolean[n][n];

        int[] count = new int[2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    dfs(i, j);
                    count[0] += 1;
                }

                if (!blindness_visited[i][j]) {
                    blindness_dfs(i, j);
                    count[1] += 1;
                }
            }
        }

        System.out.println(count[0] + " " + count[1]);
    }

    private static void dfs(int x, int y) {
        ArrayList<int[]> need_visit = new ArrayList<>();
        need_visit.add(new int[]{x, y});
        visited[x][y] = true;

        while (!need_visit.isEmpty()) {
            int[] current = need_visit.remove(need_visit.size() - 1);

            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (grid[current[0]].charAt(current[1]) == grid[nx].charAt(ny) && !visited[nx][ny]) {
                        need_visit.add(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }

    private static void blindness_dfs(int x, int y) {
        ArrayList<int[]> need_visit = new ArrayList<>();
        need_visit.add(new int[]{x, y});
        blindness_visited[x][y] = true;

        while (!need_visit.isEmpty()) {
            int[] current = need_visit.remove(need_visit.size() - 1);

            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if ((grid[current[0]].charAt(current[1]) == grid[nx].charAt(ny)
                            || (grid[current[0]].charAt(current[1]) == 'R' && grid[nx].charAt(ny) == 'G')
                            || (grid[current[0]].charAt(current[1]) == 'G' && grid[nx].charAt(ny) == 'R'))
                            && !blindness_visited[nx][ny]) {
                        need_visit.add(new int[]{nx, ny});
                        blindness_visited[nx][ny] = true;
                    }
                }
            }
        }
    }
}

 

위 풀이에서는 적록색맹인 경우와 아닌 경우를 처리하는 DFS 메소드에 중복되는 부분이 많이 있는데 이는 추후 수정할 수 있다면 수정 후 개선된 코드를 올리도록 하겠습니다... ㅎㅎ