백준 - 10026번(적록색약)

1. 문제

 

2. 풀이

BFS 방법으로 해결해 보았다. 큐를 만들어 상,하,좌,우를 탐색하면서 아직 방문하지 않았거나 같은 색깔인 경우 방문 처리 후 큐에 넣어준다. 이때, 적록색약인 경우 R과 G가 같은 색상으로 보이므로 G를 R로 바꾸거나, R을 G로 바꿔주면 된다.

다른 BFS 문제를 풀 때와 유사한 코드를 사용해 풀려고 노력했다. 그래프 탐색의 큰 틀은 비슷하게 가져가고, 문제에서 요구하는 세부 사항만 변경해 문제풀이의 일관성을 유지했다.

 

3. 코드

from collections import deque

n = int(input())
graph = [list(input()) for _ in range(n)]
visited = [[False]*n for _ in range(n)]
dx,dy = [1,0,-1,0],[0,1,0,-1]

def can_go(x,y):
    return 0<=x<n and 0<=y<n and not visited[x][y]

def bfs(x,y):
    q = deque()
    q.append((x,y))
    visited[x][y] = True

    while q:
        x,y = q.popleft()

        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]

            if can_go(nx,ny) and graph[nx][ny] == graph[x][y]:
                visited[nx][ny] = True
                q.append((nx,ny))

#적록색약이 아닌 경우
cnt1 = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i,j)
            cnt1 += 1

#적록색약인 경우
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

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

print(cnt1, cnt2)

 

📖 설명

visited = [[False]*n for _ in range(n)] 를 다시 선언해주는 이유는 visited 배열을 초기화하기 위함이다. 적록색약이 아닌 경우(cnt1)를 처리하는 동안 visited 배열의 값이 변경되었으므로, 적록색약 조건(cnt2)을 계산할 때는 새롭게 초기화해야 올바른 탐색이 가능하다.

또한, 탐색이 가능한 조건은 can_go(x, y)를 만족하고, 현재 위치의 알파벳(graph[x][y])과 다음 위치의 알파벳(graph[nx][ny])이 동일해야 한다.

 

4. 풀이-2

BFS와 같은 틀을 유지하고 코드만 DFS로 수정했다.

 

import sys
sys.setrecursionlimit(10000)

n = int(input())
graph = [list(input()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

def can_go(x, y):
    return 0 <= x < n and 0 <= y < n and not visited[x][y]

def dfs(x, y):
    visited[x][y] = True
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if can_go(nx, ny) and graph[nx][ny] == graph[x][y]:
            dfs(nx, ny)

# 적록색약이 아닌 경우
cnt1 = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j)
            cnt1 += 1

# 적록색약인 경우
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

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

print(cnt1, cnt2)

 

5. 비교

위: DFS vs 아래: BFS