https://www.acmicpc.net/problem/10026
비교적 쉬운 문제였다.
처음에 bfs 를 적록색약인 사람용 / 적록색약 아닌 사람용 => 이렇게 두 개 만들어야 하나 싶었는데,
그냥 적록색약인 사람용 그림을 새로운 리스트에 새로 선언해줘서 그거만 기존 bfs 함수에 돌렸다.
import sys
from collections import deque
input = sys.stdin.readline
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(i, j, num, map):
color = map[i][j]
q = deque()
q.append((i, j))
visit[i][j] = num
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and map[nx][ny] == color:
q.append((nx, ny))
visit[nx][ny] = num
n = int(input())
normal = [list(input().rstrip()) for _ in range(n)]
unNormal = [[''] * n for _ in range(n)]
# 적록색약용 맵 생성
for i in range(n):
for j in range(n):
if normal[i][j] == 'R':
unNormal[i][j] = 'G'
else:
unNormal[i][j] = normal[i][j]
# 적록색약이 아닌 사람이 보는 경우
answer = []
visit = [[0] * n for _ in range(n)]
normalNum = 0
unNormalNum = 0
for i in range(n):
for j in range(n):
if visit[i][j] == 0:
normalNum += 1
bfs(i, j, normalNum, normal)
answer.append(normalNum)
# 적록색약인 사람이 보는 경우
visit = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if visit[i][j] == 0:
unNormalNum += 1
bfs(i, j, unNormalNum, unNormal)
answer.append(unNormalNum)
for i in range(len(answer)):
print(answer[i], end=' ')
'알고리즘' 카테고리의 다른 글
[Algorithm] 1로 만들기 (0) | 2022.04.25 |
---|---|
[Algorithm] 떡볶이 떡 만들기 (0) | 2022.04.16 |
[Algorithm] 2589. 보물섬 (0) | 2022.04.13 |
순열 (Permutation) 알고리즘의 모든 것 (0) | 2020.05.14 |
Boj 1358. 하키 (0) | 2020.01.28 |