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

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

10026번: 적록색약

 

내 코드

import sys
input = sys.stdin.readline
from collections import deque

n =int(input())
graph = [list(input().strip('\n')) for _ in range(n)]
visited = [[0]*(n)  for _ in range(n)]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    visited[x][y]=1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<= nx < n and 0 <= ny < n:
                if not visited[nx][ny] and graph[nx][ny] == graph[x][y]:
                    visited[nx][ny] =1
                    q.append((nx, ny))

cnt1, cnt2 =0,0

#적록색약이 아닐 때
for i in range(n):
    for j in range(n):
         if not visited[i][j]:
             bfs(i, j)
             cnt1 +=1
             
#적록색약일 때
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

visited = [[0]*(n)  for _ in range(n)]            
#적록색약일 때
for i in range(n):
    for j in range(n):
         if not visited[i][j]:
             bfs(i, j)
             cnt2 +=1

print(cnt1,cnt2)

 

코드 리뷰

BFS

이 문제는 적록색약일 때와, 아닐 때를 구분하여 코드를 풀이한다. 그래서 처음에는 적록색약을 구분할 조건문을 BFS 코드 내에 넣어야 할지, FOR문으로 그래프 한 번 크게 돌릴 때 넣어야 할지 고민했다. 그런데 코드를 바꾸면 조건도 까다로워지고, 코드가 너무 길어질 것 같아서 FOR문으로 돌릴 때 구분할 수 있도록 했다.

 

def bfs(x, y):
    q = deque()
    q.append((x, y))
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    visited[x][y]=1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<= nx < n and 0 <= ny < n:
                if not visited[nx][ny] and graph[nx][ny] == graph[x][y]:
                    visited[nx][ny] =1
                    q.append((nx, ny))

cnt1, cnt2 =0,0

우선 BFS 코드이다. 여기서 주의할 부분은 그래프 자체가 숫자로 이루어져 있지 않기 때문에 문자열이든 뭐든 구분할 수 있는 코드를 하나 추가해야 한다는 점이다. 특히 현재 찾고 있는 문자가 'G'라면 다음 문자도 'G'여야 한다.

 graph[nx][ny] == graph[x][y]:

그래서 조건문을 보면 해당 조건이 추가되어 있음을 볼 수 있다.

 

#적록색약이 아닐 때
for i in range(n):
    for j in range(n):
         if not visited[i][j]:
             bfs(i, j)
             cnt1 +=1

그리고 이건 적록색약이 아닌, 평범한 경우일 때이다. 평소처럼 BFS를 돌려서 횟수를 카운팅해준다.

하지만 적록색약일 때는 그래프부터 달라진다.

#적록색약일 때
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

G와 R을 BFS 상에서 요리조리 조건문을 써서 찾는 것보다, 그래프 자체를 바꾸는게 더 쉽고 빠르다.

그래서 만약 G라고 써져있다면 적록색약은 이를 못 보니까, G를 R로 바꿔준다.

그러면 이제 R과 B의 개수만 세면 된다. 문제가 한결 쉬워진 것을 볼 수 있다.

 

visited = [[0]*(n)  for _ in range(n)]            
#적록색약일 때
for i in range(n):
    for j in range(n):
         if not visited[i][j]:
             bfs(i, j)
             cnt2 +=1

이미 한 번 VISITED 함수는 썼으니까, 다시 초기화해주는 것이 필요하다.

그리고 만약 방문하지 않았다면 방문한 후 카운팅해주면 된다.

 

적록색약을 구분할 방법을 찾기 위해 조금 헤맸는데, 어떻게 풀이하느냐에 따라 더 쉬워질 수 있다는 것을 알게 된 것 같다.