[백준] 10026번: 적록색약

문제

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

10026번: 적록색약

 

풀이

BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)를 사용해 풀었습니다.

※ 'R'과 'G'를 같은 색상으로 변환 후 탐색하는 방법도 있습니다.

 

코드

파이썬

import sys
from collections import deque

input = sys.stdin.readline

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

N = int(input())
board = [list(input()) for _ in range(N)]
visited1 = [[False] * N for _ in range(N)]
visited2 = [[False] * N for _ in range(N)]


def BFS(x, y, color_weakness):
    queue = deque()
    queue.append((x, y, color_weakness))
    while queue:
        x, y, color_weakness = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if not color_weakness:
                    if not visited1[nx][ny] and board[x][y] == board[nx][ny]:
                        visited1[nx][ny] = True
                        queue.append((nx, ny, color_weakness))
                else:
                    if not visited2[nx][ny]:
                        if board[x][y] == "B":
                            if board[x][y] == board[nx][ny]:
                                visited2[nx][ny] = True
                                queue.append((nx, ny, color_weakness))
                        else:
                            if board[nx][ny] != "B":
                                visited2[nx][ny] = True
                                queue.append((nx, ny, color_weakness))


count1 = 0
count2 = 0
for i in range(N):
    for j in range(N):
        if not visited1[i][j]:
            visited1[i][j] = True
            BFS(i, j, False)
            count1 += 1
        if not visited2[i][j]:
            visited2[i][j] = True
            BFS(i, j, True)
            count2 += 1
print(count1, count2)

import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

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

N = int(input())
board = [list(input().rstrip()) for _ in range(N)]


def DFS(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] and board[x][y] == board[nx][ny]:
                visited[nx][ny] = True
                DFS(nx, ny)


count = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            visited[i][j] = True
            DFS(i, j)
            count += 1
print(count, end=" ")

for i in range(N):
    for j in range(N):
        if board[i][j] == "G":
            board[i][j] = "R"

count = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            visited[i][j] = True
            DFS(i, j)
            count += 1
print(count)

위 코드가 pypy에서 계속 메모리 초과가 발생했는데 찾아보니 pypy는 재귀에 약하다고 한다.😂