[Python] 19237 - 어른 상어, 19238 - 스타트 택시

정환우·2022년 4월 30일
0
post-thumbnail

어른 상어

문제 링크

  • 난이도 : 골드 2

문제는 어른 상어인데, 그래도 상어 문제중에는 쉬운 편에 속하는 것 같다. 나는 청소년 상어 > 아기 상어 > 어른 상어 순으로 어려웠다. 지금 풀어도 그런 것 같다.

아 근데 이 문제를 정말 삽질을 많이 했던 부분은, 문제를 자연스럽게 읽다보니까 문제의 과정을 냄새를 뿌리고 -> 이동하는 순서로 이해를 해버렸는데,

문제를 자세히 보면 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다 라고 되어 있으며, 그 다음 과정 부터는 이동하고 -> 냄새를 뿌리는 순서로 된다.

나는 아직도 이게 왜 반례가 생기는 지는 모르겠는데, 이래서 틀린 것을 안 순간 정말 빡쳤다. 이거 그냥 코드 진짜 그대로 복사해서 순서 바꾸니까 맞았습니다가 뜨는 매직...

그래서 결론은 문제를 꼼꼼하게 읽고, 한번 더 꼼꼼하게 읽자.

방향을 미리 값을 저장해 놓고 우선순위만 잘 받아서 처리하면 된다. 냄새랑 이동은 아기 상어와 청소년 상어를 풀어보았으면 아마 제일 쉬웠을 것이다.

정답 코드

# 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)

스타트 택시

문제 링크

  • 난이도 : 골드 3

어른 상어 디버깅하는데 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)
profile
Hongik CE

0개의 댓글