[BOJ] 10026. 적록색약

www.acmicpc.net/problem/10026

10026번: 적록색약

 

문제: 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력하라.

 

문제 이해하기!!

구역을 나누는 것을 구해야 되는 문제입니다.

문제에서 나오는 적록색약은 미끼로 그냥 두 번 "R"을 "G"로 바꾸어 한 번 더 구하면 되는 문제였습니다.

그렇다면 어떻게 구역을 나눌까요.

저는 DFS로 완전탐색을 실시하였습니다.

해당 구역들을 찾기 위해서는 각 구역이 이어지는지 확인하여야 했고,

DFS 완전탐색을 통해 확인하였습니다.

BFS도 상관없으니 Stack, Queue, Recursion 등 다양한 방법으로 풀어보시면 됩니다!

 

제가 푼 방식을 설명하자면,

1. 입력을 받아 리스트 형태로 저장해주시구요.

2. "G"를 "R"로 바꾼 리스트를 하나 더 만들어줍니다.

3. 그 후, DFS를 만들고 한 번 방문한 지역은 visit에 True로 저장하여 다시 못 가게 합니다.

4. 물론, 바꾼 리스트(밑에서는 board2)에 대한 visit 배열도 따로 만들어 주고 따로 DFS를 돌려주어야 합니다.

5. 한 번 DFS가 실행될 때마다 cnt를 올려주고 각 리스트의 cnt를 출력해주면 됩니다.

 

코드:

from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)


dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
N = int(input())
board = [list(input().rstrip()) for i in range(N)]
board2 = [["R" if board[i][j] == "G" else board[i][j] for j in range(N)] for i in range(N)]
visit = [[False] * N for i in range(N)]
visit2 = [[False] * N for i in range(N)]

def dfs(x, y, p, board, visit):
    visit[x][y] = True
    for _ in range(4):
        rx = x + dxy[_][0]
        ry = y + dxy[_][1]
        if 0 <= rx < N and 0 <= ry < N:
            if board[rx][ry] == p and visit[rx][ry] == False:
                dfs(rx, ry, p, board, visit)

cnt1 = 0
cnt2 = 0
for i in range(N):
    for j in range(N):
        if visit[i][j]:
            continue
        dfs(i, j, board[i][j], board, visit)
        cnt1 += 1
        if visit2[i][j]:
            continue
        dfs(i, j, board2[i][j], board2, visit2)
        cnt2 += 1

print(cnt1, cnt2)