[Python] 23352번 방탈출

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

23352번: 방탈출

---

 

23/09/08

 

 

BFS와 브루트포스를 합친 문제로, 처음에 비효율적인 접근 방식으로 접근해서 삽질한 문제다.

---

 

문제 접근 방식:

 

 

기본적인 접근 방식은 BFS이다.

 

처음에는 시작점과 끝점의 모든 조합마다 BFS를 돌리는 방식을 택했다.

 

시간초과가 나서 보니, 경로에는 같은 점을 포함할 수도 있다는 말에 코드를 고치고 파이파이로 제출했더니 또 시간초과가 났다.

 

시작점과 끝점의 모든 조합의 최단경로마다 BFS를 돌리면 시간초과가 날 수밖에 없다.

 

총 칸은 $50 \times 50 = 2500$칸이고, 이 칸의 모든 조합을 따지면 대략 $2500^2 /2 = 3125000$번 BFS를 돌리는 셈이므로, 많은 시간을 소요하는 것이다.

 

때문에 무작정 BFS를 적용하는 대신, 다른 접근 방식을 택할 수 밖에 없었다.

 

시작점과 끝점을 선택해서 BFS를 돌리는 것이 아니라, 시작점만 택해서 BFS를 돌리고 이 시작점에서 가장 먼 점을 택하도록 코드를 고쳐주었다.

 

이러면 따로 도착점을 설정하지 않아도, 그 지점에서 가장 멀리 있는 점과의 최단 경로를 구할 수 있다.

 

따라서 최대 $2500$번만 BFS를 돌려도 충분하다.

  

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 23352번 방탈출
# BFS, 브루트포스
'''
접근 방법:
최대 N과 M의 크기가 50이므로 2500칸이다.
2500번 BFS를 톨려서 비밀번호를 구하면 된다.
'''
import sys
input = sys.stdin.readline
from collections import deque

def main():
    
    N, M = map(int, input().rstrip().split())
    A = [list(map(int, input().rstrip().split())) for _ in range(N)]
    password = 0
    max_length = 0
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]

    def BFS(sr, sc):
        if not A[sr][sc]:
            return 0, 0
        visited = set()
        queue = deque()
        visited.add((sr, sc))
        queue.append((sr, sc, 1))
        max_len = 0
        lists = []
        while queue:
            R, C, length = queue.popleft()
            if length > max_len:
                max_len = length
                lists = []
                lists.append(A[R][C])
            elif length == max_len:
                lists.append(A[R][C])
            for i in range(4):
                nr, nc = R+dr[i], C+dc[i]
                if 0 <= nr < N and 0 <= nc < M and A[nr][nc] != 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, length+1))
        return A[sr][sc]+max(lists), max_len

    for start in ((i, j) for i in range(N) for j in range(M)):
        pwd, leng = BFS(start[0], start[1])
        if leng > max_length:
            password = pwd
            max_length = leng
        elif leng == max_length:
            if pwd > password:
                password = pwd
                
    print(password)
    return

main()