문제
이 문제는 전형적인 구역 개수 구하기 에서 살짝 변형된 문제이다.
적록색약 환자가 보는 그림을 구해준다음에 두 그림에 대해서 구역의 개수를 구해주는 방식으로 문제를 풀었다.
이때 유의할 점이 있는데 적록색약 환자가 보는 그림을 만들어줄 때 원래의 그림을대입하고 대입해준 리스트를 이중 for문을 돌면서 녹색을 적색으로 바꾸어주려고 했는데
rg_paint = paint
이렇게 해주면 두 리스트가 같은 메모리를 차지하게 되므로 paint의 부분도 바뀌게 된다.
따라서 리스트를 단순히 대입하는 것이 아닌 값을 하나하나씩 받아서 삽입해주어 해당 문제를 해결해주었다.
나의 코드
from collections import deque
n = int(input())
paint = [list(input()) for _ in range(n)]
#적녹색약 환자가 보는 그림
rg_paint = [['']*n for _ in range(n)]
for i in range(n):
for j in range(n):
if paint[i][j] == 'G':
rg_paint[i][j] = 'R'
else:
rg_paint[i][j] = paint[i][j]
visited = [[0]*n for _ in range(n)]
rg_visited = [[0]*n for _ in range(n)]
#같은 색상을 가졌고 상하좌우로 이어진 좌표를 방문처리하는 함수
def count(paint,visited,a,b,key):
q = deque()
q.append((a,b))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited[a][b] == 1
while(q):
x,y = q.popleft()
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
#좌표값이 범위내에 있고 방문한 적없고 처음 주어진 색상이랑 같은색이여야함
if 0<= nx <n and 0<= ny <n and visited[nx][ny] == 0 and paint[nx][ny] == key:
q.append((nx,ny))
visited[nx][ny] = 1
return visited
cnt1 =0
cnt2 = 0
for i in range(n):
for j in range(n):
if visited[i][j] == 0:
visited = count(paint, visited, i,j,paint[i][j])
cnt1 += 1
if rg_visited[i][j] == 0:
rg_visited = count(rg_paint,rg_visited, i,j,rg_paint[i][j])
cnt2 += 1
print(cnt1,cnt2)구역의 개수를 구하는 방법은 방문한적없는 좌표가 있다면
그 좌표와 같은 구역인 좌표들을 전부 방문 처리 해준 후 ->
다시 방문한 적없는 좌표만 방문해주면서 좌표를 방문할 때마다 카운트를 해주면 된다.
