[Python] BOJ(백준) 10026번 - 적록색약

1. 링크

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

2. 난이도(solved.ac 참고)

골드5

3. 풀이

	# https://www.acmicpc.net/problem/10026
	from collections import deque
	n = int(input())
	visited = [[False] * n for _ in range(n)]
	map_example = [list(map(str, input())) for _ in range(n)]
	queue = deque()
	dx = [-1, 1, 0, 0]
	dy = [0, 0, -1, 1]
	def bfs(x, y):
	queue.append([x, y])
	while queue:
	x, y = queue.popleft()
	for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and map_example[nx][ny] == map_example[x][y]:
	queue.append([nx, ny])
	visited[nx][ny] = True
	count = 0
	for i in range(n):
	for j in range(n):
	if not visited[i][j]:
	bfs(i, j)
	count += 1
	print(count, end=' ')
	# 색약자 케이스
	for i in range(n):
	for j in range(n):
	if map_example[i][j] == 'R':
	map_example[i][j] = 'G'
	visited = [[False] * n for _ in range(n)] # 다시 초기화해주고 진행해야됨
	count = 0
	for i in range(n):
	for j in range(n):
	if not visited[i][j]:
	bfs(i, j)
	count += 1
	print(count)

view raw 적록색약.py hosted with ❤ by GitHub

색약자가 아닌 경우에 일반적인 BFS를 진행하여 visited를 사용하고, 그다음 색약자에 대한 조건을 설정한 후(R을 G로 바꾸기) visited를 다시 초기화한 뒤 BFS를 진행했다.

BFS에서 x,y좌표를 움직였을 때 그 부분이 방문되지 않았고(not visited) 이전 값과 같은 경우(둘다 R이거나 둘다 G이거나 둘다 B이거나) 큐에 넣고 방문처리를 한 뒤(visited[nx][ny] = True) 다시 반복문을 돌았다.