23352번 - 방탈출

널널한 시간제한

이번문제는 코드가 상당히 더티합니다.
그 이유는

이렇게 배열 크기가 50 X 50 이라는 넉넉한 사이즈로 주셨기에
시간제한을 염두할 필요 없이 배열의 복사 및 탐색을 거리낌없이 사용하여 풀이할 수 있었습니다.
물론 깔끔하고 빠르게 푼다면 좋겠지만 그건 실력이 되는 사람들 이야기고 저는 골드문제 푸는 것만으로 감지덕지...

BFS

BFS는 어려울 것 없이 항상 먹던 그 맛입니다.
그래프를 모두 1로 바꿨으니 현재거리 + 1을 다음 거릿값에 대입해주면 됩니다.

from collections import deque
import sys
import copy

input = sys.stdin.readline

que,sys,copy등 라이브러리를 선언하고

dx = [-1,1,0,0]
dy = [0,0,1,-1]

상하좌우 지정한 다음에

def bfs(x,y):
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue 

상하좌우 탐색 중 그래프를 넘어가면 continue로 스킵해주고

            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                que.append([nx,ny])

만약 다음 탐색지점이 1이라면 현재 탐색지점 + 1을 다음 탐색지점에 넣어주고 다음 탐색지점으로 넘어갑니다.
다만 이런씩으로 작성하면 첫 시작지점이 다시 참조되어 변수가 오염되므로

   if graph[i][j] != 0:
        bfs(i,j)
        graph[i][j] = 1

아까 위에서 graph[i][j]를 1로 초기화해준 이유가 이런 연유입니다.

    return [x,y]

마지막으로 종점값을 리턴값으로 잡으면 됩니다.

기본 선언

이번문제 접근 형식을 간단히 설명드리겠습니다.
먼저 BFS로 시작점~종점까지 다 탐색한 후, 그 거리를 도출합니다.
해당 거리값이 가장 크다면 시작과 종점에 해당되는 인덱스 값을 더하여 리턴하면 끝입니다.

N,M = map(int,input().split())
que = deque()
graph = []
for _ in range(N):
    graph.append(list(map(int,input().split())))
graph_copy = copy.deepcopy(graph)

일단 BFS 사용을 위해서 기본적인 que와 그 외 것들을 받아주겠습니다.

for i in range(N):
    for j in range(M):
        if graph[i][j] != 0:
            graph[i][j] = 1

그리고 시작점~종점 거릿값 탐색을 위해 인덱스 값은 잠시 graph_copy에 넣어두고 0(막힌구간)을 제외한 나머지 인덱스는 죄다 1로 바꾸겠습니다.

graph_copy_distance = copy.deepcopy(graph)
max_distance = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] != 0:
            bfs(i,j)
            graph[i][j] = 1
            if max_distance <= max(map(max,graph)):
                max_distance = max(map(max,graph))
            graph = copy.deepcopy(graph_copy_distance)

탐색을 시작합니다.
graph_copy_distance에 아까 죄다 1로 만든 그래프를 복사해주고
각 인덱스마다 bfs 탐색을 돌려서 시작점부터 종점까지의 거릿값을 측정해줍니다.
그리고 max_distance에 최대로 나온 거릿값을 대입합시다.

ans = []
ans_tmp = 0
for p in range(N):
    for k in range(M):
        if graph[p][k] != 0:
            [ans_x,ans_y] = bfs(p,k)
            graph[p][k] = 1
            ans_tmp = 0
            if max(map(max,graph)) == max_distance:
                ans_tmp += graph_copy[p][k]
                ans_tmp += graph_copy[ans_x][ans_y]
            graph = copy.deepcopy(graph_copy_distance)
        ans.append(ans_tmp)

이제 다시 탐색을 돌아 종점을 bfs return 값으로 받아오고 만약 현재 탐색중인 그래프가 거릿값의 최대를 보여준다면
시작점과 종점을 ans_tmp에 담아 ans배열에 추가해주도록 합시다.

try:
    print(max(ans))
except:
    print(0)

이렇게 만들어진 ans_tmp의 집합중에서 가장 큰 값을 출력하면 답이 나옵니다.