알고리즘 - Python / 백준 - 10026번 : 적록색약

10026번: 적록색약 (acmicpc.net)

10026번: 적록색약

 

---

풀이

• 익숙한 형태의 일반적인 그래프 탐색 문제다.
• 2차원 배열 형태의 상하좌우가 연결되어 있으므로 , visited를 잘 체크하면서 bfs, dfs를 사용하면 된다.
• 문제의 포인트라면 적록색약의 경우 R = G 인 경우인데 , 적록색약이 아닌 경우를 bfs로 구한 이후에 새롭게 적록색약 배열을 만들어 준 후 다시 bfs를 진행하여 답을 찾았다.
• 새로운 적록색약 배열은 전체 2차원 배열을 순회하면서 R인 경우 G로 일일이 바꾸어 주었다.
• bfs 코드 상에서 세팅을 해서 굳이 이런 과정을 거치지 않고도 할 수 있겠지만 , N이 최대 100인 케이스라 별 상관없다고 느꼈다.

 

import sys
from collections import deque
n = int(sys.stdin.readline())
c = [["x" for _ in range(n+2)]]
for _ in range(n):
    c.append(["x"] + list(sys.stdin.readline().replace("\n","")) + ["x"])
c.append(["x" for _ in range(n+2)])
ans = 0
visited = [[0 for i in range(n+2)] for _ in range(n+2)]
def bfs(start_y,start_x):
    global visited
    root = deque()
    root.append([start_y,start_x])
    returns = 0
    if visited[start_y][start_x] == 0:
        returns = 1
    while root:
        n = root.popleft()
        if visited[n[0]][n[1]] == 0:
            visited[n[0]][n[1]] = c[n[0]][n[1]]
            if c[n[0]][n[1]+1] == c[n[0]][n[1]]:
                root.append([n[0],n[1]+1])
            if c[n[0]][n[1]-1] == c[n[0]][n[1]]:
                root.append([n[0],n[1]-1])
            if c[n[0]+1][n[1]] == c[n[0]][n[1]]:
                root.append([n[0]+1,n[1]])
            if c[n[0]-1][n[1]] == c[n[0]][n[1]]:
                root.append([n[0]-1,n[1]])
    return returns

ans = 0
ans_rg = 0
for i in range(1,n+1):
    for t in range(1,n+1):
        ans += bfs(i,t)

for i in range(1,n+1):
    for t in range(1,n+1):
        if c[i][t] == "R":
            c[i][t] = "G"
visited = [[0 for i in range(n+2)] for _ in range(n+2)]
for i in range(1,n+1):
    for t in range(1,n+1):
        ans_rg += bfs(i,t)
print(ans,end=" ")
print(ans_rg)

 

---