🚩 코딩테스트/알고리즘
[백준] 10026번: 적록색약
딩딩크롱
2023. 5. 11. 01:42
728x90
문제
https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
풀이
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는 재귀에 약하다고 한다.😂
728x90