[백준 파이썬] #2146. 다리만들기

풀기 전 생각해보기😮

• 간척 사업 아이디어 적용해보기
• 중복해서 인식되는 지점을 어떻게 해결할 것인지
• 메모리 초과 오류 발생 해결

---

풀이🛫

from collections import deque

dcol = [1, 0, -1, 0]
drow = [0, 1, 0, -1]


def divide_island():
    cnt = 1
    # 주어진 arr의 모든 부분 탐색 시도
    for col in range(N):
        for row in range(N):
            if arr[col][row] == 1:      # 어느 한 섬에 도달하면
                cnt += 1                # 몇 번째 섬인지 표시하기 위해 cnt 활용
                queue = deque()             # BFS 진행
                queue.append((col, row))
                checked[col][row] = 1

                while queue:
                    # 메모리 체크
                    # print(len(queue), queue)
                    # print(len(border_lst), border_lst)

                    for i in range(len(queue)):
                        col, row = queue.popleft()
                        arr[col][row] = cnt
                        flag = 0                    # 중복해서 border_lst에 들어가는 것을 방지하기 위한 체커

                        for v in range(4):
                            ncol = col+dcol[v]
                            nrow = row+drow[v]
                            if 0<=ncol<N and 0<=nrow<N:
                                if arr[ncol][nrow] and checked[ncol][nrow] == 0:
                                    arr[col][row] = cnt
                                    checked[ncol][nrow] = 1
                                    queue.append((ncol, nrow))

                                if arr[ncol][nrow] == 0:
                                    if flag > 0:
                                        continue
                                    border_lst.append((col, row))
                                    flag += 1


def expand():
    global answer

    queue = deque()
    queue.extend(border_lst)
    cnt = 0
    while queue:
        # 메모리 체크
        # print(queue)
        cnt += 1
        for i in range(len(queue)):
            col, row = queue.popleft()
            for v in range(4):
                ncol = col + dcol[v]
                nrow = row + drow[v]
                if 0<=ncol<N and 0<=nrow<N:
                    if arr[ncol][nrow] == 0 and visited[ncol][nrow] == 0:
                        arr[ncol][nrow] = arr[col][row]
                        visited[ncol][nrow] = cnt
                        checked[ncol][nrow] = 1
                        queue.append((ncol, nrow))

                    if arr[col][row] != arr[ncol][nrow]:
                        if visited[col][row] == 0 and visited[ncol][nrow]:
                            temp = visited[ncol][nrow]
                        elif visited[ncol][nrow] == 0 and visited[col][row]:
                            temp = visited[col][row]
                        else:
                            temp = visited[col][row] + visited[ncol][nrow]

                        if answer > temp:
                            answer = temp

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
checked = [[0]*N for _ in range(N)]
answer = 0xfff
border_lst = []
ans_lst = []


divide_island()
expand()


print(answer)

 

핵심 정리🎁

# 1
print(len(queue), queue)      # 메모리 체크
print(len(border_lst), border_lst)

# 2
if arr[ncol][nrow] == 0:
    if flag > 0:
        continue
    border_lst.append((col, row))
    flag += 1

• 채점 과정중 46%였던가..? 에서 멈칫하더니 메모리초과 또는 시간초과 오류가 계속해서 발생했다.
  (반례 질문하시는 분들 중에서도 같은 위치에서 고민하시는 분들이 꽤 보였다)
• 결과값도 잘 나오고 굳이 문제될 곳이 없는 것 같아 꽤나 고민을 길게 했었는데, #1번과 같이 queue의 변화와 border_lst를 찍어보고나서 중복되는 값이 삽입된다는 점을 발견했다.
  
  • 해결을 위해 간단히 flag 변수를 이용하였고, flag 변수가 1이상일 경우, continue로 넘어가도록 설정했다

 

링크💎

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

2146번: 다리 만들기

 

후기 😎

• 단순하게(or 무식하게) 접근하는 방법으로도 풀린다고 한다.
  그렇지만 시간이 꽤 나온다고 하니 간척사업 아이디어를 배울 수 있었단 점에서  
• 메모리 초과를 겪는다면, stack이나 queue를 print 해서 살펴보도록 하자