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

그래프, bfs / 골드 5

❤️💚

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

10026번: 적록색약

 

 

내 풀이

from collections import deque

def bfs(x, y):
    global area

    q = deque()
    q.append((x,y))
    visited[x][y] = True
    color = arr[x][y] # 현재 색
    area += 1

    while q:
        cx, cy = q.popleft()
        
        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]

            if 0 <= nx < N and 0 <= ny < N and arr[nx][ny] == color and not visited[nx][ny]: # 인덱스가 범위를 벗어나지 않았고, 현재 색과 동일한 색이며, 아직 방문하지 않은 곳일 떄
                visited[nx][ny] = True
                q.append((nx, ny))


N = int(input())
arr = [[] * N for _ in range(N)]
visited = [[False] * N for _ in range(N)]
ans = []
area = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(N):
    arr[i] = list(input())

# 일반 사람이 보는 경우
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)

ans.append(area)
area = 0
visited = [[False] * N for _ in range(N)]

# G -> R로 변경
for i in range(N):
    for j in range(N):
        if arr[i][j] == 'G':
            arr[i][j] = 'R'
            
# 적록색약인 사람이 보는 경우
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)

ans.append(area)

print(*ans)

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

bfs를 호출해 일반 사람이 보는 구역의 개수를 먼저 검사한다.

# 일반 사람이 보는 경우
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)

 

area: 구역의 개수

visited: 검사한 구역인지 아닌지를 구별하는 리스트

정답리스트(ans)에 구역의 개수(area)를 추가해 준 뒤, 구역의 개수(area)와 visited를 초기화한다.

ans.append(area)
area = 0
visited = [[False] * N for _ in range(N)]

 

적록색약인 사람이 바라보게 될 색상대로 arr를 변경한다. 💚 ➡ ❤️

# G -> R로 변경
for i in range(N):
    for j in range(N):
        if arr[i][j] == 'G':
            arr[i][j] = 'R'

 

bfs를 다시 호출해 적록색약인 사람이 보는 구역의 개수를 검사한 뒤, 정답리스트에 추가한다.

# 적록색약인 사람이 보는 경우
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)

ans.append(area)

 

 

✔️ bfs 함수

 

인덱스가 범위를 벗어나지 않았고, 현재 색과 동일한 색이며, 아직 방문하지 않은 곳인 경우에만

방문처리 후 deque에 해당 좌표를 추가한다.

현재 색과 다른 색을 만난 경우, 무시한다.

if 0 <= nx < N and 0 <= ny < N and arr[nx][ny] == color and not visited[nx][ny]:
    visited[nx][ny] = True
    q.append((nx, ny))