[백준] 10026번: 적록색약 (파이썬)

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

 

기본적인 BFS 문제에 자잘한 조건이 추가된 문제이다.

일반인과 적록색약의 graph를 따로 만들어서 bfs를 돌렸다.

 

from collections import deque

n = int(input())
graph_i = [] #일반인
graph_j = [] #적록색약
for _ in range(n):
    temp = list(input())
    graph_i.append(temp[:])
    graph_j.append(temp[:])

#적록색약 graph
for i in range(n):
    for j in range(n):
        if graph_j[i][j] == 'G':
            graph_j[i][j] = 'R'

#방향
dx = [0,-1,0,1]
dy = [1,0,-1,0]

visited_i = [ [-1] * n for _ in range(n)] #일반인 방문 리스트
visited_j = [ [-1] * n for _ in range(n)] #적록색약 방문 리스트

result_i = 0 #일반인 결과
result_j = 0 #적록색약 결과


def bfs(i,j,graph,visited):
    queue = deque([(i,j)])

    while queue:
        x,y = queue.popleft()
        visited[x][y] = 1
        for k in range(4):
            current_x, current_y = x + dx[k], y + dy[k]
            if 0 <= current_x < n and 0 <= current_y < n and graph[current_x][current_y] == graph[x][y] and visited[current_x][current_y] == -1:
                visited[current_x][current_y] = 1
                queue.append((current_x,current_y))

#일반인
for i in range(n):
    for j in range(n):
        if visited_i[i][j] == -1:
            bfs(i,j,graph_i,visited_i)
            result_i += 1

#적록색약
for i in range(n):
    for j in range(n):
        if visited_j[i][j] == -1:
            bfs(i,j,graph_j,visited_j)
            result_j += 1

print(result_i,result_j,end='')

처음에

graph_i.append(temp)

graph_j.append(temp)

라고 했는데, 이상하게 graph_j를 변경했는데 graph_i도 같이 변경됐었다.

알고보니까 같은 temp를 참조해서 그런 것이었다.

 

bfs의 엄청긴 조건문 이후에 visited[current_x][current_y]의 방문처리를 해주지 않아서 불필요한 탐색이 계속되어서 메모리 초과가 났다.

기본적인 문제였는데, 자잘한 조건들이 있어서 얻어가는 것이 있는 것 같다!