[백준_23352] 방탈출 python

# n, m 입력
n, m = map(int, input().split())

# room 입력
room = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들
# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

# can_go(x, y)
def can_go(x, y):
    # 범위 내에 있고, 방문한 적 없으며, 0이 아니면 가능
    return in_range(x, y) and not visited[x][y] and room[x][y]

# bfs()
def bfs():
    while q:
        x, y = q.popleft()
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            # 다음 위치로 갈 수 있으면,
            if can_go(nx, ny):
                q.append((nx, ny))
                visited[nx][ny] = 1
                step[nx][ny] = step[x][y] + 1

# 설계
# 큐 사용 준비
from collections import deque
q = deque()

# 각 케이스마다 최장거리와 시작 끝 합을 담아 줄 리스트
pin_num_list = []

# 방을 돌면서,
for i in range(n):
    for j in range(m):
        
        # 0이 아닌 방을 만나면,
        if room[i][j]:
            
            # visited 설계 및 초기화
            visited = [
                [0] * m
                for _ in range(n)
            ]

            # step 설계 및 초기화
            step = [
                [0] * m
                for _ in range(n)
            ]

            # bfs
            q.append((i, j))
            visited[i][j] = 1
            bfs()

            # start_num 설정
            start_num = room[i][j]

            # max_dist 설정
            max_dist = 0

            # 현 케이스의 최대 거리 찾기
            for a in range(n):
                for b in range(m):
                    if step[a][b] > max_dist:
                        max_dist = step[a][b]
            
            # 최대 거리에 해당하는 거리와 값을 
            for a in range(n):
                for b in range(m):
                    # pin_num_list에 담아주기
                    if step[a][b] == max_dist:
                        pin_num_list.append([max_dist, start_num + room[a][b]])
            
# pin_num_list 내림차순 정렬
pin_num_list.sort(reverse=True)

# 출력
# 비밀번호를 만들 수 없으면,
if len(pin_num_list) == 0:
    print(0)
# 만들 수 있으면,
else:
    print(pin_num_list[0][1])