문제는 어른 상어인데, 그래도 상어 문제중에는 쉬운 편에 속하는 것 같다. 나는 청소년 상어 > 아기 상어 > 어른 상어 순으로 어려웠다. 지금 풀어도 그런 것 같다.
아 근데 이 문제를 정말 삽질을 많이 했던 부분은, 문제를 자연스럽게 읽다보니까 문제의 과정을 냄새를 뿌리고 -> 이동하는 순서로 이해를 해버렸는데,
문제를 자세히 보면 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다 라고 되어 있으며, 그 다음 과정 부터는 이동하고 -> 냄새를 뿌리는 순서로 된다.
나는 아직도 이게 왜 반례가 생기는 지는 모르겠는데, 이래서 틀린 것을 안 순간 정말 빡쳤다. 이거 그냥 코드 진짜 그대로 복사해서 순서 바꾸니까 맞았습니다가 뜨는 매직...
그래서 결론은 문제를 꼼꼼하게 읽고, 한번 더 꼼꼼하게 읽자.
방향을 미리 값을 저장해 놓고 우선순위만 잘 받아서 처리하면 된다. 냄새랑 이동은 아기 상어와 청소년 상어를 풀어보았으면 아마 제일 쉬웠을 것이다.
# 1의 번호를 가진 상어는 모두를 쫓아낼 수 있다.
# 1. 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다.
# 2. 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 그 칸에 냄새를 뿌린다.
# 냄새는 상어가 k번 이동하면 사라진다.
# 상어 이동방향 결정 방법
#
# 1. 아무 냄새가 없는 칸
# 2. 그런 칸이 없으면 자신의 냄새가 있는 칸
# 여러 칸인 경우 : 특정한 우선순위를 따른다. 상어마다 다르고, 같은 상어도 방향마다 다르다.
N, M, K = map(int, input().split())
graph = []
sharks = [[] for _ in range(M)]
for _ in range(N):
graph.append(list(map(int, input().split())))
shark_graph = [[[] for _ in range(N)] for _ in range(N)]
for ky in range(N):
for kx in range(N):
if graph[ky][kx] != 0:
shark_graph[ky][kx].append(graph[ky][kx])
shark_dir = list(map(int, input().split()))
smell = [[0] * N for _ in range(N)]
for s in range(M):
sharks[s].append([])
for _ in range(4):
inp2 = list(map(int, input().split()))
sharks[s].append(inp2)
smell_count = [[0] * N for _ in range(N)]
for y in range(N):
for x in range(N):
# 상어가 없으면
if not shark_graph[y][x]:
continue
# 현재 좌표에 냄새부터 뿌린다.
smell[y][x] = shark_graph[y][x][0]
smell_count[y][x] = K
# sharks : 0~3번 상어의 방향 우선순위. 1~4 : 위 아 왼 오 향할 때 우선순위
# graph 에는 상어 번호가 1~4번으로 나타나있음을 주의!!!!!!
def check(now_x, now_y):
if 0 <= now_x < N and 0 <= now_y < N:
return True
return False
def move():
global N
global shark_graph
global shark_dir
global smell
global smell_count
global K
delta = [[0, 0], [-1, 0], [1, 0], [0, -1], [0, 1]] # 위 아래 왼쪽 오른쪽 (y,x)
tmp = [[[] for _ in range(N)] for _ in range(N)]
for y in range(N):
for x in range(N):
# 상어가 없으면
if not shark_graph[y][x]:
continue
shark_num = shark_graph[y][x].pop() - 1
# 상어의 현재 방향
now_dir = shark_dir[shark_num]
# 움직였으면 True로 바꿔줘야 한다.
is_move = False
# 우선순위로 확인
for direct in sharks[shark_num][now_dir]:
ny = y + delta[direct][0]
nx = x + delta[direct][1]
if not check(nx, ny):
continue
# 냄새가 없는 칸으로 움직이는 경우
if smell_count[ny][nx] <= 0:
tmp[ny][nx].append(shark_num + 1)
shark_dir[shark_num] = direct
is_move = True
break
# 움직였으면 다음 상어 확인
if is_move:
continue
# 빈 칸이 없으면, 자신의 냄새가 있는 칸으로 방향을 잡는다.
for direct in sharks[shark_num][now_dir]:
ny = y + delta[direct][0]
nx = x + delta[direct][1]
if not check(nx, ny):
continue
# 자신의 냄새가 있는 칸인 경우
if shark_num + 1 == smell[ny][nx]:
tmp[ny][nx].append(shark_num + 1)
shark_dir[shark_num] = direct
break
# 모든 상어 이동 끝. 냄새 없애고 냄새 뿌린다.
for yy in range(N):
for xx in range(N):
if smell_count[yy][xx] > 0:
smell_count[yy][xx] -= 1
if smell_count[yy][xx] == 0:
smell[yy][xx] = 0
if len(tmp[yy][xx]) == 1:
smell[yy][xx] = tmp[yy][xx][0]
smell_count[yy][xx] = K
continue
if not tmp[yy][xx]:
continue
min_shark = M + 1
while tmp[yy][xx]:
now_num = tmp[yy][xx].pop()
min_shark = min(now_num, min_shark)
# 가장 작은 상어 한마리만 살아 남는다.
tmp[yy][xx].append(min_shark)
smell[yy][xx] = tmp[yy][xx][0]
smell_count[yy][xx] = K
shark_graph = tmp
answer = 0
while True:
move()
answer += 1
if answer > 1000:
answer = -1
break
count = 0
for ky in range(N):
for kx in range(N):
if shark_graph[ky][kx]:
count += 1
if count == 1:
break
print(answer)
어른 상어 디버깅하는데 2시간이 걸려서, 한 시간도 안 남은 채로 이 문제를 들어갔는데 30분 말에 진짜 빡집중해서 풀어버린 문제다.
카카오 덕에 다익스트라가 단련이 되어있어서 쉽게 풀은 것 같기도 하다.
택시 좌표 기준으로 다익스트라를 이용해 모든 좌표의 최단 거리를 구한다. 거기서 가장 가까운 승객을 찾는다. 여기서 주의할점은 벽을 충분히 큰 값으로 두어서 최단 거리 > 벽 이 되는 경우가 없어야 한다.
그래서 그 좌표를 다시 택시 좌표로 잡고 도착 좌표까지 다익스트라 거리 값을 구하고, 도착 좌표를 다시 택시 좌표로 잡는다.
그러니까 택시 좌표의 변화는 처음 좌표로 시작해서,
승객 좌표 -> 승객 집 좌표 -> 승객 좌표 -> 승객 집 좌표
이렇게 무한 반복하고, 이때 가지 못하는 경우가 있으면 예외처리를 해주면 되는 것이다.
그리고, 예상했듯이 완전히 벽으로 막혀서 승객한테 가지 못하거나 승객이 도착하지 못하는 경우가 있는데, 이 경우까지 예외처리를 해주면 된다.
그러면 깔끔하게 시간초과도 안나고 끝!
import heapq
N,M,answer = map(int,input().split())
graph = []
for _ in range(N):
graph.append(list(map(int,input().split())))
ds_y, ds_x = map(int,input().split()) # 운전 시작하는 행열 번호
target = []
for _ in range(M):
target.append(list(map(int,input().split())))
def check(x,y):
if 0<=x<N and 0<=y<N:
return True
return False
# 최단 거리 구하기
def dikjstra(x,y):
global graph
delta = [[-1,0],[1,0],[0,1],[0,-1]]
q = []
heapq.heappush(q, [0,x,y])
distance = [[100] * N for _ in range(N)]
distance[y][x] = 0
while q:
cost,x,y = heapq.heappop(q)
for d in delta:
nx = x + d[0]
ny = y + d[1]
if not check(nx,ny):
continue
if graph[ny][nx] == 1:
continue
if distance[ny][nx] > cost + 1:
distance[ny][nx] = cost + 1
heapq.heappush(q, [cost+1, nx, ny])
return distance
ds_x -= 1
ds_y -= 1
while True:
if len(target) == 0:
break
start_dist = dikjstra(ds_x,ds_y)
q = []
for i in range(len(target)):
sy,sx,dy,dx = target[i]
heapq.heappush(q, [start_dist[sy-1][sx-1], sy-1, sx-1, dy-1, dx-1, i])
# 최단거리 승객 고름
start_fuel, sy, sx, dy, dx, idx = heapq.heappop(q)
if start_fuel == 100:
answer = -1
break
target = target[:idx] + target[idx+1:] #target에서 삭제
# 승객한테 까지 가는 연료 : start_fuel
end_dist = dikjstra(sx,sy)
# 승객 목적지까지 가는 연료
end_fuel = end_dist[dy][dx]
if end_fuel == 100:
answer = -1
break
# 연료가 바닥나는 경우
if start_fuel + end_fuel > answer:
answer = -1
break
# 연료 두배 충전
answer += end_fuel - start_fuel
ds_x = dx
ds_y = dy
print(answer)