백준16569(화산쇄설류) - python 해결

화산쇄설류

 

문제

화산학자 윤재상은 어느 화산섬을 탐사하러 갔다가 곧 섬에 있는 화산들이 곧 폭발하기 시작할 것이라는 급보와 각 화산의 폭발 시점 정보를 받았다.

섬은 M행 N열의 행렬로 표현된다. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t 라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 재상인 빨리 탈출을 하고싶다.

• 재상이는 처음에 X행 Y열에 있다.
• 재상이는 단위 시간 당 상하좌우 한 칸만 움직일 수 있다.
• 재상이는 화산이 있는 위치와 화산쇄설류가 뒤덮인 곳은 갈 수 없다.

재상이는 화산쇄설류를 피해서 되도록 가장 높은 곳으로 피하고 싶고, 되도록 가장 빨리 도달하기를 원한다. 재상이가 화산쇄설류를 피해서 도달할 수 있는 가장 높은 고도와, 그 고도까지 도달하는데 걸리는 최소 시간을 구한다.

 

입력

첫 번째 줄에 정수 M, N, V이 공백으로 구분되어 주어진다. (1 ≤ M, N ≤ 100, 1 ≤ V ≤ min(5,000, M×N))

그 다음 줄에 X, Y가 공백으로 구분되어 주어진다. (1 ≤ X ≤ M, 1 ≤ Y ≤ N)

그 다음 줄부터 M개의 줄마다 N개의 공백으로 구분된 수들이 주어진다. i행 j열의 값은 (i, j) 지대의 고도 hij 를 나타낸다. (0 ≤ hij ≤ 10,000)

그 다음 줄부터 V개의 줄이 주어진다. i번째 줄에 xi, yi, ti가 공백으로 구분되어 주어진다. 이 수들은 i번째 화산의 위치 (xi, yi,)와 화산의 분출시각 ti를 의미한다. (1 ≤ xi ≤ M, 1 ≤ yi ≤ N, 0 ≤ ti ≤ 200)

위치, 시간, 고도 수치들은 모두 정수이다. X행 Y열에 화산이 있는 입력은 주어지지 않는다.

 

출력

재상이가 도달할 수 있는 최고 높이와 그 높이에 도달할 수 있는 최단 시간을 공백을 구분하여 출력한다.

---

구현 문제라 조금 고민을 많이했다.

시간을 기준으로 탐색하는 방식을 사용했다.

사람은 1초단위로 움직이고 화산은 그 시간에 터지는 걸 기준으로 하였다.

그걸 위해서 화산은 2차 리스트로 시간인덱스로 두고 값은 화산들의 위치를 표현하였다.

그리고 사람은 같은 시간대의 위치는 모두 같이 움직이도록 만들었다.

그리고 제출했을 때 끝에 인덱스 초과가 난다. 이 문제는 화산 저장을 0~200초 까지만 저장했는데 그 이상이 있을 수 있다는 것이다.

해당 관련 글 : https://www.acmicpc.net/board/view/31724

글 읽기 - 데이터 추가 요청합니다.

또 한가지 더 문제는 https://www.acmicpc.net/board/view/35528

글 읽기 - 반례를 알려주세요 ㅜㅜ

화산의 위치도 움직일 수 없는 것으로 만들어여야하는데 화산의 방문 배열에 넣으면 위와 같은 문제가 발생하고 아니면 이동할 수 있는 문제가 생겨서 사람의 방문 배열에 추가하여 이동하지 못하도록하였다.

 

import sys
input = sys.stdin.readline

M, N, V = map(int,input().split())
X, Y = map(int,input().split())
X -= 1
Y -= 1
maps = [list(map(int,input().split())) for _ in range(M)]
# 화산, 사람 방문 배열
vol_visit = [[0] * N for _ in range(M)]
per_visit = [[0] * N for _ in range(M)]

# 화산 시간에 따라 저장 200까지 하면 인덱스 에러 나오기 때문에
# 더크게 잡아야한다.
volcanos = [[] for _ in range(300)]
for _ in range(V):
    vol = list(map(int,input().split()))
    # 시간대에 
    volcanos[vol[2]].append([vol[0]-1,vol[1]-1])
    # 화산 위치는 움직일 수 없기 때문
    per_visit[vol[0]-1][vol[1]-1] = 1

# 사람 q
per_q = [[X,Y]]
# 답을 위해서 
max_h = maps[X][Y]
max_t = 0
# 시간
t = 0

dirs = [[-1,0],[0,1],[1,0],[0,-1]]
# 탐색
while per_q:
    # 화산재 이동
    for vol_loc in volcanos[t]:
        # 방문시
        if vol_visit[vol_loc[0]][vol_loc[1]]:
            continue
        vol_visit[vol_loc[0]][vol_loc[1]] = 1
        # 이동
        for dir in dirs:
            next_vol_loc_x = vol_loc[0] + dir[0]
            next_vol_loc_y = vol_loc[1] + dir[1]

            if 0 <= next_vol_loc_x < M and 0 <= next_vol_loc_y < N:
                pass
            else:
                continue

            if vol_visit[next_vol_loc_x][next_vol_loc_y]:
                continue

            volcanos[t+1].append([next_vol_loc_x,next_vol_loc_y])
    
    # 사람 이동
    next_per_q = []
    for per_loc in per_q:
        # 방문과 화산
        if per_visit[per_loc[0]][per_loc[1]]:
            continue
        if vol_visit[per_loc[0]][per_loc[1]]:
            continue
        per_visit[per_loc[0]][per_loc[1]] = 1
        # 결과 확인
        if maps[per_loc[0]][per_loc[1]] > max_h:
            max_h = maps[per_loc[0]][per_loc[1]]
            max_t = t
        # 이동
        for dir in dirs:
            next_per_loc_x = per_loc[0] + dir[0]
            next_per_loc_y = per_loc[1] + dir[1]

            if 0 <= next_per_loc_x < M and 0 <= next_per_loc_y < N:
                pass
            else:
                continue
            if per_visit[next_per_loc_x][next_per_loc_y]:
                continue
            if vol_visit[next_per_loc_x][next_per_loc_y]:
                continue

            next_per_q.append([next_per_loc_x,next_per_loc_y])
            
    per_q = next_per_q[:]
    # 시간 증가
    t += 1

print(max_h,max_t)