BOJ 16469 - 소년 점프

문제

백준 온라인 저지 - 16469번

풀이 과정

넉살, 스윙스, 창모 세 사람의 좌표가 주어질 때 마미손 이 위치할 수 있는 좌표를 찾는 문제입니다.

맨 처음 접근 방법은 마미손 은 세 사람이 모일 수 있는 한 좌표까지의 거리 값이 가장 짧은 곳에 위치하기 때문에
이를 위해서 각 점에 대해서 다익스트라 알고리즘으로 최단 거리를 계산했었습니다.
그러나 이 경우 시간 복잡도가 O(V^2*ElogV) 이기 때문에 시간 초과가 발생하였고, 다른 방법으로의 접근이 필요했습니다.

생각해보면 모든 좌표에서 다익스트라 를 수행할 필요 없이 그냥 넉살, 스윙스, 창모 세 사람을 기준으로 탐색을 수행한 다음,
각 좌표들에 대해서 거리 최댓값끼리 비교해주면 됩니다.

따라서 그냥 BFS 를 이용해서 세 사람을 시작지점으로 하는 탐색을 수행하고, 거리 값을 dist 3차원 배열에 기록했습니다.
넉살, 스윙스, 창모 각각은 0, 1, 2 라는 id 값으로 구분해줬습니다.

코드

import sys
from collections import deque

R, C = list(map(int, sys.stdin.readline().split()))
maze = [list(sys.stdin.readline().strip()) for _ in range(R)]
nucksal = list(map(int, sys.stdin.readline().split()))
swings = list(map(int, sys.stdin.readline().split()))
changmo = list(map(int, sys.stdin.readline().split()))

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]


def in_range(r, c):
    return 0 <= r < R and 0 <= c < C


def bfs(id, r, c, dist):
    visit = [[0] * C for _ in range(R)]
    q = deque()

    dist[r][c][id] = 0
    visit[r][c] = 1
    q.append([r, c, 0])

    while q:
        r, c, cost = q.popleft()

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if in_range(nr, nc) and not visit[nr][nc] and maze[nr][nc] == '0':
                dist[nr][nc][id] = cost + 1
                visit[nr][nc] = 1
                q.append([nr, nc, cost + 1])

    return sys.maxsize


def solution():
    dist = [[[-1] * 3 for _ in range(C)] for _ in range(R)]

    for id, [r, c] in enumerate([nucksal, swings, changmo]):
        bfs(id, r - 1, c - 1, dist)

    min_cost, count = sys.maxsize, 0
    for r in range(R):
        for c in range(C):
            if all(map(lambda x: x != -1, dist[r][c])):
                cost = max(dist[r][c])
                if cost < min_cost:
                    min_cost = cost
                    count = 1
                elif cost == min_cost:
                    count += 1

    if min_cost != sys.maxsize:
        print(min_cost, count, sep='\n')
    else:
        print(-1)

solution()