[Python] 백준 10026번 : 적록색약

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

10026번: 적록색약

---

 문제 풀이

BFS 문제이다.

 

이런 류의 문제는 항상 고민해야 하는 것이 BFS/DFS를 돌려서 어떻게 결과를 낼 것인지 이다.

우선 색약이 있는 사람과 없는 사람을 따로 구분해서 2차원 배열을 구현해줬다. 

2차원 배열을 돌면서 방문하지 않은 곳을 기준으로 더 이상 이동할 수 없을 때 하나의 구역으로 인지한다.

 느낀 점

DFS 문제를 풀어보려고 골랐는데 또 BFS 였다. 어떻게 탐색을 해서 결과를 낼 지만 고민한다면 그렇게 어렵지 않은 문제이다.

 코드

import sys

N = int(sys.stdin.readline())
board = [sys.stdin.readline().strip() for _ in range(N)]
nboard = [[] for _ in range(N)]

for i in range(N):
    nboard[i] = board[i].replace('G','R')

moves = [(-1,0), (1,0), (0,-1), (0,1)]
visited = [[False] * N for _ in range(N)]

def BFS(x, y, bd):
    queue = [[x,y]]
    
    while queue:
        x, y = queue.pop(0)
        
        for i in range(4):
            nx, ny = x + moves[i][0], y + moves[i][1]
            
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and bd[x][y] == bd[nx][ny]:
                    queue.append([nx, ny])
                    visited[nx][ny] = True
                
cnt = 0
for x in range(N):
    for y in range(N):
        if not visited[x][y]:
            BFS(x, y, board)
            cnt += 1
print(cnt, end=' ')

cnt = 0
visited = [[False] * N for _ in range(N)]
for x in range(N):
    for y in range(N):
        if not visited[x][y]:
            BFS(x, y, nboard)
            cnt += 1
print(cnt)