[Python] BOJ/백준 10026번 적록색약

[문제]

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

10026번: 적록색약

 

[풀이]

딱봐도 탐색문제..~

내가 계속 BFS로 풀어서 DFS로도 한번 풀어봤다

 

계속 까먹어서 적어두는데

BFS는 deque를 이용해 풀고

DFS는 재귀 호출을 이용해 푼다.

공통점은 둘 다 visited를 이용해서 해당 칸 방문 여부를 검사했다.

 

[BFS 코드]

import sys
from collections import deque

n = int(sys.stdin.readline())
section = [list(sys.stdin.readline()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
three_count, two_count = 0, 0

# 방향 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        current_color = section[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if current_color == section[nx][ny] and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

# 적록색약이 아닌 사람
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            three_count += 1

# 일반 그림을 적록색약이 보이는 그림으로 변환
for i in range(n):
    for j in range(n):
        if section[i][j] == 'R':
            section[i][j] = 'G'

# 적록색약
visited = [[False] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            two_count += 1

print(three_count, two_count)

 

 

[DFS 코드]

import sys
sys.setrecursionlimit(1000000)

three_count, two_count = 0, 0
n = int(sys.stdin.readline())
section = [list(input().rstrip()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

# 방향 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
    visited[x][y] = True
    current_color = section[x][y]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if not visited[nx][ny]:
                if current_color == section[nx][ny]:
                    dfs(nx, ny)

# 적록색약이 아닌 사람
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j)
            three_count += 1

# 일반 그림을 적록색약이 보이는 그림으로 변환
for i in range(n):
    for j in range(n):
        if section[i][j] == 'R':
            section[i][j] = 'G'

# 적록색약
visited = [[False] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j)
            two_count += 1

print(three_count,two_count)