<BOJ>10026번: 적록색약

문제

10026번: 적록색약

접근

  • BFS 코드 틀을 알고 있으면 쉽게 풀 수 있는 전형적인 BFS 문제이다.
  • 현재 좌표와 다음 좌표의 색상이 같으면 이동하는 방식으로 탐색한다.
  • 2중 for문으로 방문하지 않은 좌표인지 파악해서 해당 좌표에서 BFS를 호출한다. 이 때 카운팅을 한다. → 각 색상별로 영역이 몇 개인지 파악함
  • 적록색약인 경우를 위해 G영역을 R영역으로 바꾸고, visited를 초기화 한 뒤 다시 탐색한다.

내 코드

from collections import deque

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

n = int(input())
grid = [list(input()) for _ in range(n)]
q = deque()

visited = [[False] * n for _ in range(n)]
count = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            count += 1

for i in range(n):
    for j in range(n):
        if grid[i][j] == 'G':
            grid[i][j] = 'R'

visited = [[False] * n for _ in range(n)]
blind = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            blind += 1

print(count, blind)

좋은 웹페이지 즐겨찾기