[백준] [USACO-Bronze] [Python] 적록색약 - BFS

www.acmicpc.net/problem/10026

10026번: 적록색약

 

 

 

Python

from collections import deque

n = int(input())
img = []
for _ in range(n):
    img.append(input())

dx = [0,0,1,-1]
dy = [1,-1,0,0]

ok = deque()
visit = [[0]*n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if visit[i][j] != 0:
            continue
        ok.append([i,j])
        visit[i][j] = 1
        color = img[i][j]
        cnt += 1
        
        while ok:
            pos = ok.popleft()
            #print(pos)
            for ii in range(4):
                nx = pos[0]+dx[ii]
                ny = pos[1]+dy[ii]
                if 0<=nx<n and 0<=ny<n:
                    if img[nx][ny] == color and visit[nx][ny] == 0:
                        visit[nx][ny] = visit[pos[0]][pos[1]]+1
                        ok.append([nx,ny])

print(cnt, end=" ")

nok = deque()
visit = [[0]*n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if visit[i][j] != 0:
            continue
        nok.append([i,j])
        visit[i][j] = 1
        color = img[i][j]
        cnt += 1
        
        while nok:
            pos = nok.popleft()
            #print(pos)
            for ii in range(4):
                nx = pos[0]+dx[ii]
                ny = pos[1]+dy[ii]
                if 0<=nx<n and 0<=ny<n and visit[nx][ny] == 0:
                    if (color == "B" and img[nx][ny] == color) or (color!="B" and img[nx][ny] != "B"):
                            visit[nx][ny] = visit[pos[0]][pos[1]]+1
                            nok.append([nx,ny])
  
print(cnt)

 

 

짧은 풀이

- 적록색약인 사람

파란색은 파란색인지 확인하면 되고, 

빨간색과 초록색은 구분은 파란색이 아닐 때로 기준을 두어 한 꺼번에 고려할 수 있게 함.