tlov
백준 10026 | 적록색약 [파이썬] 본문
https://www.acmicpc.net/problem/10026
풀이
문제 보고 두 가지 해결방안이 떠올랐다.
첫 번째는 주어진 입력으로 적록색약이 아닌 사람이 봤을 때 구역 수를 먼저 구한 뒤에 그리드 내의 R 또는 G를 한 가지 색으로 통일시켜 적록색약인 사람의 구역 수를 구하는 방법
두 번째는 BFS로 돌리면서 현재 색이 R 또는 G 일 때, 상하좌우도 R 또는 G 면 큐에 넣어 구역 수를 구하는 방법
어쨌든 둘 다 적어도 그래프 탐색을 두 번 호출해야 해결할 수 있다.
코드
import sys, copy
from collections import deque
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N = int(input())
grid = [list(input().rstrip()) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
wasd = ((0, -1), (0, 1), (-1, 0), (1, 0))
def dfs(x, y, color):
visited[y][x] = True
for hx, hy in wasd:
hx += x
hy += y
if (hx >= 0 and hx < N) and (hy >= 0 and hy < N):
if not visited[hy][hx] and grid[hy][hx] == color:
dfs(hx, hy, color)
def bfs(blindess):
queue = deque()
copy_visited = copy.deepcopy(visited)
cnt = 0
for i in range(N):
for j in range(N):
if not copy_visited[i][j]:
queue.append([j, i])
copy_visited[i][j] = True
while queue:
xx, yy = queue.popleft()
for hx, hy in wasd:
hx += xx
hy += yy
if (hx >= 0 and hx < N) and (hy >= 0 and hy < N):
if blindess and (not copy_visited[hy][hx]):
if grid[yy][xx] == 'G' or grid[yy][xx] == 'R':
if grid[hy][hx] == 'G' or grid[hy][hx] == 'R':
queue.append([hx, hy])
copy_visited[hy][hx] = True
else:
if grid[hy][hx] == grid[yy][xx]:
queue.append([hx, hy])
copy_visited[hy][hx] = True
else:
if not copy_visited[hy][hx] and grid[hy][hx] == grid[yy][xx]:
queue.append([hx, hy])
copy_visited[hy][hx] = True
cnt += 1
return cnt
cnt = 0
for i in range(N):
for j in range(N):
if not visited[i][j]:
dfs(j, i, grid[i][j])
cnt += 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)]
blindcnt = 0
for i in range(N):
for j in range(N):
if not visited[i][j]:
dfs(j, i, grid[i][j])
blindcnt += 1
print(cnt, blindcnt)
# bfs 정답
# print(bfs(False))
# print(bfs(True))
'알고리즘 문제' 카테고리의 다른 글
3190 - 뱀 [성공(반례힌트)|02:14:43] (0) | 2024.08.09 |
---|---|
백준 12094 - 2048 (Hard) [파이썬] (0) | 2022.11.22 |
백준 12100 - 2048 (Easy) [파이썬] (0) | 2022.11.20 |
백준 1541 - 잃어버린 암호 [자바] (0) | 2022.10.31 |
백준 2206 | 벽 부수고 이동하기 [파이썬] (0) | 2022.08.09 |