[BOJ][Python]10026번 풀이

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

10026번: 적록색약

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

def sol():
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                q.append((i,j))
                visited[i][j] = 1
                c = t[i][j]
                while q:
                    tmp = q.popleft()
                    for k in dp:
                        if 0 <= tmp[0]+k[0] < n and 0 <= tmp[1]+k[1] < n:
                            if visited[tmp[0]+k[0]][tmp[1]+k[1]] == 0:
                                if t[tmp[0]+k[0]][tmp[1]+k[1]] == c:
                                    q.append((tmp[0]+k[0], tmp[1]+k[1]))
                                    visited[tmp[0]+k[0]][tmp[1]+k[1]] = 1
                ans[0] += 1
            else:
                continue
                                              
def sol1():
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 1:
                q.append((i,j))
                visited[i][j] = 0
                c = t[i][j]
                while q:
                    tmp = q.popleft()
                    for k in dp:
                        if 0 <= tmp[0]+k[0] < n and 0 <= tmp[1]+k[1] < n:
                            if visited[tmp[0]+k[0]][tmp[1]+k[1]] == 1:
                                if c == 'R' or c == 'G':
                                    if t[tmp[0]+k[0]][tmp[1]+k[1]] == 'B':
                                        continue
                                    else:
                                        q.append((tmp[0]+k[0], tmp[1]+k[1]))
                                        visited[tmp[0]+k[0]][tmp[1]+k[1]] = 0
                                else:
                                    if t[tmp[0]+k[0]][tmp[1]+k[1]] == c:
                                        q.append((tmp[0]+k[0], tmp[1]+k[1]))
                                        visited[tmp[0]+k[0]][tmp[1]+k[1]] = 0
                ans[1] += 1
            else:
                continue
            
n = int(ssr())
t = [list(ssr()) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
q = deque([])
dp = [(-1,0),(1,0),(0,-1),(0,1)]
ans=[0,0]
sol()
sol1()
print(*ans)

좀 더 고민하면 더 보기 좋게 짤 수 있을 것 같기는 한데 방법이 잘 떠오르질 않네요. 주어지는 N의 범위가 100까지 밖에 안되다보니 최대한도로 돌아도 20000번 밖에 돌지 않아서 탐색을 두 번 하는 방법을 이용했는데 좋은 방법이 생각나면 한 번 고쳐보겠습니다.

 

문제 접근은 기본적인 그래프 탐색입니다. dfs/bfs 둘 다 사용가능하구요. 코드의 직관성은 dfs쪽이 좋을 것으로 생각되네요. 일단 문제의 출력은 적녹색약이 아닌 사람이 봤을 때의 구역과 적녹색약이 봤을 때의 구역을 따로 출력해줘야합니다. 그래서 저는 경우에 따라 각각 탐색을 진행해줬습니다. sol()은 아닌 사람, sol1()은 적녹색약의 경우입니다. 저는 bfs로 구성을 했기 때문에 deque를 사용합니다. 일단 주어진 입력을 하나씩 탐색하는 이중반복문을 작성하고 그 내부에서 방문처리가 안된 좌표에 대해서 bfs를 진행합니다. 큐가 다 비워지면 한 구역을 다 돌았다는 뜻이니 구역의 숫자를 1 증가 시켜줍니다. 적녹색약의 경우는 R과 C를 같은 것으로 취급하기 때문에 그런 조건에 맞춰서 bfs를 진행해줍니다. B 구역일 경우에는 sol()과 동일해도 무방합니다.