소년 점프

🤔 접근

3명의 위치에서 각각 BFS로 탐색해주면 되는 문제이다.

처음엔 visited 테이블 하나로 해결을 해보려고 했지만, 3차원 배열이 오히려 더 헷갈리는 것 같아서 각각 visited 테이블을 생성해주었다.

A, B, C의 위치에서 출발하여 bfs로 각 위치까지 얼마나 걸리는지 기록한 다음, 마지막에 모든 위치를 순회하면서 A, B, C가 모두 방문할 수 있는지와 방문할 수 있다면 가장 오래걸린 사람이 몇 초 걸렸는지를 확인해주면 풀린다.

단, 이렇게 해결하면 답을 찾았음에도 계속 탐색하게 되어 min_time이 짧아도 시간복잡도는 table크기에 따라 정해지게 된다.

💻 코드

# 16469
import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
table = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]
visited_A = [[-1] * M for _ in range(N)]
visited_B = [[-1] * M for _ in range(N)]
visited_C = [[-1] * M for _ in range(N)]

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))



def bfs(visited, start):
    x, y = start
    visited[x][y] = 0
    q = deque([(x, y)])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M and (visited[nx][ny] == -1) and table[nx][ny] == 0:
                q.append((nx, ny))
                visited[nx][ny] = visited[x][y] + 1
    return visited

bfs(visited_A, (A[0]-1, A[1]-1))
bfs(visited_B, (B[0]-1, B[1]-1))
bfs(visited_C, (C[0]-1, C[1]-1))

min_time = 1e9
res = []
for i in range(N):
    for j in range(M):
        a = visited_A[i][j]
        b = visited_B[i][j]
        c = visited_C[i][j]
        if a == -1 or b == -1 or c == -1:
            continue
        
        if min_time > max(a, b, c):
            res = [[i, j]]
            min_time = max(a, b, c)

        elif min_time == max(a, b, c):
            res.append([i, j])
        
if len(res):
    print(min_time)
    print(len(res))
else:
    print(-1)