2146 파이썬

해당 문제를 풀면서 겪었던 문제들을 되짚어보고자 작성했습니다

문제를 풀기 위해서는 크게 2개의 과정을 생각해야 합니다.
1. 섬에 대한 구분을 어떻게 해줄지 고민하다가 지체 없이 섬들끼리의 구분을 주기 위해 1과 0으로만 입력된 섬과 바다의 구분을 섬에 대해서 2, 3, 4 .. 등으로 그룹핑시켰습니다.

>마치 scc 방식이라고도 생각이 듭니다(?) 

완전히 같은 개념은 아니지만 이 생각을 들고 위 과정을 거쳤습니다.

2. 바다를 건너 만난 다른 육지까지의 최소의 바다 칸의 개수를 구하기 위해 bfs를 생각했습니다. 여기까진 괜찮았습니다.

   dx =[ 1, -1, 0, 0]
   dy = [0, 0, -1, 1] 로 4개의 방향을 체크하고 출발한 육지와는 다른 육지라면 최소 다리인지 체크해주는 작업을 진행했고, 바다라면 이전 바다 칸에 저장된 다리 개수에 1을 더한걸 저장해줍니다.

맞는 방식이라 판단했고, 인터넷 상에 존재하는 테스트케이스를 대입한 결과 모두 맞다고 떴습니다. 하지만 "메모리 초과" 에러가 50%에서 계속 났습니다.
저의 문제의 코드입니다.

import sys 
from collections import deque
import copy
val = int(input())
dx =[ 1, -1, 0, 0]
dy = [0, 0, -1, 1]
map_loc = []
#visited = []
for i in range(val):
    map_loc.append(list(map(int, sys.stdin.readline().rstrip().split())))
    #visited.append(map_loc[i])
cnt = 0
queue = deque()
x = 0 
flag = 1
end_x, end_y = 0 , 0 
# visited = {}
# visited[-1] = 1
for x in range(val):
    for y in range(val):
        if map_loc[x][y] == 1:
            queue.append((x,y))
            flag +=1 # scc 형태로 표현 
            # visited[flag] = 0
            while queue:
                loc_x , loc_y = queue.popleft()
                end_x, end_y = loc_x, loc_y
                map_loc[loc_x][loc_y] = flag 
                for i in range(4):
                    x_t = loc_x + dx[i]
                    y_t = loc_y + dy[i]
                    if 0<= x_t and x_t < val and 0<=y_t and y_t < val:
                        if map_loc[x_t][y_t]==1:
                            queue.append((x_t, y_t))
            # print(end_x, end_y)
# for i in range(val):
#     for j in range(val):
#         print(map_loc[i][j],end=' ')
#     print()
# print()
min_val = val*2
def bfs(min_val,map_info):
    map_l = copy.deepcopy(map_info)
    # print(map_loc)
    queue = deque()
    for x in range(val):
        for y in range(val):
            if map_l[x][y] != 0 and map_l[x][y]!= -1:
                # print(map_loc[x][y])
                # visited[map_loc[x][y]] = 1
                queue.append((x,y,0, map_l[x][y]))
                
                while queue:
                    loc_x , loc_y, dist , flag= queue.popleft()
                    if min_val > dist:
                        # print(loc_x, loc_y,dist, flag)
                        for i in range(4):
                            x_t = loc_x + dx[i]
                            y_t = loc_y + dy[i]
                            if 0<= x_t and x_t < val and 0<=y_t and y_t < val:
                                if map_l[x_t][y_t] == 0:
                                    # print("appended",x_t, y_t, dist+1, flag)
                                    queue.append((x_t, y_t, dist+1, flag))
                                    map_l[x_t][y_t] = -1
                                elif map_l[x_t][y_t] != flag and map_l[x_t][y_t] != -1 and map_l[x_t][y_t] != 0 and map_l[x_t][y_t] != map_l[loc_x][loc_y]:
                                    
                                    min_val = min(min_val, dist)
                                    # print("found dist:",dist,"min val:",min_val,flag, map_l[x_t][y_t], map_l[loc_x][loc_y],[x_t,y_t],[loc_x,loc_y])
                                    # for n in range(val):
                                    #     for m in range(val):
                                    #         print(map_l[n][m],end=' ')
                                    #     print()
                                    
    return min_val
print(bfs(min_val, map_loc))
# print(min_val)

위 코드에서 2개의 실수를 저질렀습니다. (사실 더 많습니다..)
1. 처음 섬들을 구분해주는 작업에서 visited를 쓰지 않아, 갔던 곳을 또 가는 작업이 발생한 것입니다.
2. bfs 함수에서 deepcopy를 쓴 점이 문제였습니다. visited라는 새로운 배열을 할당해서 방문한 노드인지 체크해주는 방식을 썼어야했는데, deepcopy가 메모리 초과 문제에 영향을 끼칠 수도 있다는 생각을 하지 않았던 점이 문제였습니다.

이를 해결한 코드는 아래와 같습니다.

import sys 
from collections import deque

val = int(input())
dx =[ 1, -1, 0, 0]
dy = [0, 0, -1, 1]
map_loc = []
visited = [[False]*val for _ in range(val)]
for i in range(val):
    map_loc.append(list(map(int, sys.stdin.readline().rstrip().split())))
    # visited.append(map_loc[i])

queue = deque()

flag = 1

for x in range(val):
    for y in range(val):
        if map_loc[x][y] == 1 and visited[x][y] == False:
            visited[x][y] =True
            queue.append((x,y))
            flag +=1 # scc 형태로 표현 
            # visited[flag] = 0
            while queue:
                loc_x , loc_y = queue.popleft()
               
                end_x, end_y = loc_x, loc_y
                map_loc[loc_x][loc_y] = flag 
                for i in range(4):
                    x_t = loc_x + dx[i]
                    y_t = loc_y + dy[i]
                    if 0<= x_t < val and 0<=y_t < val and map_loc[x_t][y_t]==1 and visited[x_t][y_t] ==False :
                        visited[x_t][y_t] =True
                        queue.append((x_t, y_t))
            # print(end_x, end_y)
# for i in range(val):
#     for j in range(val):
#         print(map_loc[i][j],end=' ')
#     print()
# print()
min_val = val*2
def bfs(status_island,min_val,map_info,val):
    # print("{}".format(status_island))
    # map_l = copy.deepcopy(map_info)
    # check = set()
    map_l = map_info
    # print(map_loc)
    dist= [[-1 for _ in range(val)] for _ in range(val)]
    queue = deque()
    for x in range(val):
        for y in range(val):
            if map_l[x][y] == status_island :
                dist[x][y] = 0
                queue.append([x,y])

    while queue:
        loc_x , loc_y= queue.popleft()
       
        # print(loc_x, loc_y,dist, flag)
        for i in range(4):
            x_t = loc_x + dx[i]
            y_t = loc_y + dy[i]
            if 0<= x_t and x_t < val and 0<=y_t and y_t < val:
                # print(visited[x_t][y_t])
                # if visited[x_t][y_t] ==0 and  map_l[x_t][y_t] == 0:
                if map_l[x_t][y_t] == 0 and dist[x_t][y_t]== -1:
                    # print("appended",x_t, y_t, dist+1, flag)
                    # check.add((x_t, y_t))
                    dist[x_t][y_t] = dist[loc_x][loc_y] + 1
                    queue.append([x_t, y_t])
                    
                elif map_l[x_t][y_t] != status_island and map_l[x_t][y_t] > 0:
                    dist[x_t][y_t] = dist[loc_x][loc_y] + 1
                    # dist[x_t][y_t] =1
                    min_val = min(min_val, dist[loc_x][loc_y])
                    return min_val
                                                            
    return min_val
# print("F",flag)
for i in range(2,flag+1):
    # print("i",i)
    return_val = bfs(i, min_val,map_loc, val)
    min_val = min(min_val, return_val)
print(min_val)
# print(min_val)

dist라는 새로운 배열을 써서 deque에 들어가는 데이터의 개수도 줄였고, 맨 처음 섬을 그룹핑하는 과정에서도 visited를 써서 중복 방문을 없앴습니다. 이때, 저는 기존에 visited =[0 or 1]로 표현했는데, bool로 습관을 바꾸게 되었습니다. (메모리에 민감해지기 시작한 코린이입니다..ㅎ)
또한 visited에 true로 바꾸는 방식은 queue에서 pop할때가 아니라, 처음 queue에 들어갈때 해줘야 메모리초과가 안 났습니다. (이건 자세한 이유는 몰라서 혹시 아신다면 조언해주시면 감사하겠습니다!)