Python/BFS BOJ-10026 적록색약

Posted on | In

[Python/BFS] BOJ-10026 적록색약

📌문제링크

적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하면 된다.
방문여부를 체크하자.

BFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import copy
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(x,y,cnt,board,visited):
    q = deque([])
    q.append((x,y))
    visited[x][y] = cnt
    while q :
        x,y = q.popleft()
        for i in range(4):
            nx= x+ dx[i]
            ny= y+ dy[i]
            if 0<= nx < N and 0 <= ny <N :
                if board[x][y] == board[nx][ny] and visited[nx][ny] ==0 : # 색상이 같아야함
                    visited[nx][ny] = cnt
                    q.append((nx,ny))
    return cnt

if __name__ == '__main__':
    N = int(input())
    board =[list(input().rstrip()) for _ in range(N)]
    RGboard =copy.deepcopy(board)
    for x in range(N) :
        for y in range(N) :
            if RGboard[x][y] == 'G':
                RGboard[x][y] = 'R'
    dx =[-1,1,0,0]
    dy=[0,0,-1,1]
    # Normal case
    visited = [[0]*N for _ in range(N)]; cnt = 0
    for x in range(N):
        for y in range(N):
            if visited[x][y]==0 :
                cnt += 1
                normal = dfs(x,y,cnt,board,visited)
    # Color blindness case
    visited = [[0]*N for _ in range(N)]; cnt = 0
    for x in range(N):
        for y in range(N):
            if visited[x][y]==0 :
                cnt += 1
                color_blind = dfs(x,y,cnt,RGboard,visited)
    print('{} {}'.format(normal, color_blind))