[백준 22955번] 파이썬 - 고양이 도도의 탈출기

백준 22955 - 고양이 도도의 탈출기

시간 제한 5초(추가 시간 x), 메모리 제한 1024MB(추가 메모리 x)

# 조건

• 고양이 도도가 강아지들을 피해 탈출구를 찾아 방을 탈출하려 하고 있다.
• 고양이 도도는 현재 위치한 공간의 상태에 따라 다음과 같이 움직일 수 있다.
• 고양이가 위치한 곳에 사다리가 존재하거나 고양이가 위치한 곳이 아래가 뚫려있는 공간이 아닌 상태에서 고양이가 위치한 곳의 아래 칸에 사다리가 존재한다면 각각 위 칸과 아래 칸으로 이동할 수 있고 사다리를 이용하여 한 칸 이동할 시 5만큼의 체력이 소모된다.
• 고양이가 위치한 곳이 아래가 뚫려 있는 공간이라면 고양이는 아래에 있는 바닥 중 가장 처음 마주한 바닥에 착지하게 되며 이때 10만큼의 체력이 소비된다.
• 고양이가 아래가 뚫려 있는 공간에 위치해 있지 않을 경우, 좌우로 1칸씩 이동할 수 있으며 1칸 이동할 시 1만큼의 체력이 소비된다.
• 이 때, 평평한 바닥 위에서의 이동과 사다리 타기, 바닥으로 착지하는 행동은 별개의 행동으로 본다.
• 예시로 고양이 도도가 사다리가 있는 위치로 1칸 이동한 후 사다리를 타고 1칸을 올라간다면 총 6만큼의 체력이 소비된다.
• 고양이 도도가 체력을 가장 적게 소비하며 탈출하고자 할 때 고양이 도도는 얼마의 체력으로 탈출할 수 있을까?

입력

• 첫째 줄에 방의 높이 N(2<=N<=1000)과 방의 너비 M(2<=M<=1000)이 주어진다.
• 둘째 줄부터 N개의 줄에 공간의 상태가 주어진다.
• 공간의 상태는 C, D, E, F, L, X로 이루어져 있고, 아래와 같은 의미를 가진다.
  • C: 고양이 도도
  • D: 강아지
  • E: 탈출구
  • F: 일반 바닥
  • L: 사다리
  • X: 아래가 뚫려있는 공간
• 고양이와 탈출구는 방안에 각각 하나씩 있으며 아래가 뚫려있는 공간을 제외하고는 모든 위치에 평평한 바닥이 존재한다.
• 가장 아래 바닥의 경우에는 아래가 뚫려 있는 공간이 올 수 없다.

출력

• 고양이 도도가 체력을 가능한 적게 소비하며 방을 탈출하려 할 때, 총 얼마의 체력으로 방을 탈출할 수 있을지 소비된 체력을 출력한다.
• 방을 탈출하지 못할 경우에는 dodo sad를 출력한다.

# 접근 방법

• bfs를 돌려 출구에 도착하는 모든 곳을 비교해준다면 시간초과가 발생한다.
• 다익스트라와 딕셔너리를 활용하여 시간을 줄여줄 필요가 있다.
• 우선 고양이가 출발하는 위치와 도착위치, 사다리 위치와 내려간 지점 또는 올라가는 지점, 낙하시 도착 지점을 기록해준다.
• bfs를 돌리는데 우선순위 큐를 이용하여, 소비되는 체력을 기준으로 넣어준다.
• 또한, 방문 한 경우 현재 기록된 cnt가 visited에 기록된 값 보다 크다면 continue 해준다.
• 주의해야 될 점은 사다리가 있는 칸인 경우 올라가는 것은 선택이다.
  • 내려오는 경우도..
  • 또한, 시작 위치에 사다리가 있는 경우도 고려하지 않았다.. 항상 출발위치 찾고 땅과 같이 일반적인 경우로 변경해주기.. !

시간 초과

• 매번 체크하는 과정을 반복해주니 시간 초과가 발생하였다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappush, heappop  
INF = float('inf')  

def dijkstra(ci, cj):  
    q = [(0, ci, cj)]  
    visited[ci][cj] = 0  
    while q:  
        val, si, sj = heappop(q)  
        if arr[si][sj] == 'E':  
            print(val)  
            return  
        if visited[si][sj] < val:  
            continue  

        # 평지인 경우 현재 위치에서 내려갈 수 있는 사다리 있는지 체크  
        # 좌우 체크        
        if arr[si][sj] == 'F':  
            for j in [-1, 1]:  
                ni, nj = si, sj + j  
                if 0<=nj<M and arr[ni][nj] != 'D':  
                    if visited[ni][nj] > val + 1:  
                        visited[ni][nj] = val + 1  
                        heappush(q, (val+1, ni, nj))  

            # 사다리 있는지 체크  
            if (si, sj) in fall_ladder:  
                ni, nj = fall_ladder[(si, sj)]  
                if visited[ni][nj] > val + 5:  
                    visited[ni][nj] = val+5  
                    heappush(q, (val+5, ni, nj))  

        # 사다리인 경우  
        # 올라가는 경우와 내려갈 수 있는 경우, 좌우 체크        
        elif arr[si][sj] == 'L':  
            for j in [-1, 1]:  
                ni, nj = si, sj + j  
                if 0 <= nj < M and arr[ni][nj] != 'D':  
                    if visited[ni][nj] > val + 1:  
                        visited[ni][nj] = val+1  
                        heappush(q, (val + 1, ni, nj))  

            # 사다리 있는지 체크  
            if (si, sj) in climb_ladder:  
                ni, nj = climb_ladder[(si, sj)]  
                if visited[ni][nj] > val + 5:  
                    visited[ni][nj] = val+5  
                    heappush(q, (val + 5, ni, nj))  

            # 사다리 있는지 체크  
            if (si, sj) in fall_ladder:  
                ni, nj = fall_ladder[(si, sj)]  
                if visited[ni][nj] > val + 5:  
                    visited[ni][nj] = val + 5  
                    heappush(q, (val + 5, ni, nj))  


        # 바닥이 없는경우  
        # 떨어지고 나서 사다리가 있는지 체크        
        elif arr[si][sj] == 'X':  
            if (si, sj) in fall:  
                ni, nj = fall[(si,sj)]  
                if visited[ni][nj] > val + 10:  
                    visited[ni][nj] = val + 10  
                    heappush(q, (val + 10, ni, nj))  



    print('dodo sad')  
    return  



N, M = map(int, input().split())  
arr = [list(input().rstrip()) for _ in range(N)]  

fall_ladder = dict()  
climb_ladder = dict()  
fall = dict()  

# 순회하며 출발, 도착 위치와  
# 사다리를 타고 올라가는 경우, 내려오는 경우  
# 떨어지는 곳이라면 낙하지점을 기록해준다.  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] == 'C':  
            ci, cj = i, j  
            arr[i][j] = 'F'  
        elif arr[i][j] == 'E':  
            ei, ej = i, j  
        elif arr[i][j] == 'L':  
            # 올라간 곳이 땅 또는 사다리이면 기록  
            if 0<= i-1 and arr[i - 1][j] != 'X' and arr[i - 1][j] != 'D':  
                fall_ladder[(i-1, j)] = (i, j)  
                climb_ladder[(i, j)] = (i-1, j)  
        elif arr[i][j] == 'X':  
            li = i  
            flag = True  
            while arr[li][j] == 'X':  
                li += 1  
                if arr[li][j] == 'D':  
                    flag = False  
                    break            if flag:  
                fall[(i, j)] = (li, j)  
visited = [[INF] * M for _ in range(N)]  

dijkstra(ci, cj)

pass

• 매번 딕셔너리를 찾아보는 것이 아닌 평지와 사다리인 경우 좌우 + 아래, 좌우 + 위 아래를 주어진 배열에서 바로바로 찾도록 하였다.
• 또한, 떨어지는 곳도 배열에 표시해주어 바로바로 이동하도록 해주었다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappush, heappop  
INF = float('inf')  

def dijkstra(ci, cj):  
    q = [(0, ci, cj)]  
    visited[ci][cj] = 0  
    while q:  
        val, si, sj = heappop(q)  
        if arr[si][sj] == 'E':  
            print(val)  
            return  
        if visited[si][sj] < val :  
            continue  

        # 평지인 경우 현재 위치에서 내려갈 수 있는 사다리 있는지 체크  
        # 좌우 체크        
        if arr[si][sj] == 'F':  
            for j in [-1, 1]:  
                ni, nj = si, sj + j  
                if 0<=nj<M and arr[ni][nj] != 'D':  
                    if visited[ni][nj] > val + 1:  
                        visited[ni][nj] = val + 1  
                        heappush(q, (val+1, ni, nj))  
            if 0<= si+1 < N and arr[si+1][sj] == 'L':  
                if visited[si+1][sj] > val+5:  
                    visited[si+1][sj] = val + 5  
                    heappush(q, (val+5, si+1, sj))  


        # 사다리인 경우  
        # 올라가는 경우와 내려갈 수 있는 경우, 좌우 체크        
        elif arr[si][sj] == 'L':  
            for j in [-1, 1]:  
                ni, nj = si, sj + j  
                if 0 <= nj < M and arr[ni][nj] != 'D':  
                    if visited[ni][nj] > val + 1:  
                        visited[ni][nj] = val+1  
                        heappush(q, (val + 1, ni, nj))  

            if 0<=si+1< N and arr[si+1][sj] == 'L':  
                if visited[si+1][sj] > val + 5:  
                    visited[si+1][sj] = val+ 5  
                    heappush(q, (val+5, si+1, sj))  

            if 0<=si-1<N and arr[si-1][sj] != 'D' and arr[si-1][sj] != 'X':  
                if visited[si-1][sj] > val + 5:  
                    visited[si-1][sj] = val+5  
                    heappush(q, (val+5, si-1, sj))  

        # 바닥이 없는경우  
        else:  
            ni = arr[si][sj][0]  
            nj = arr[si][sj][1]  
            if visited[ni][nj] > val + 10:  
                visited[ni][nj] = val + 10  
                heappush(q, (val+10, ni, nj))  



    print('dodo sad')  
    return  



N, M = map(int, input().split())  
arr = [list(input().rstrip()) for _ in range(N)]  

fall = []  
# 순회하며 출발위치와  
# 떨어지는 곳이라면 낙하지점을 기록해준다.  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] == 'C':  
            ci, cj = i, j  
            arr[i][j] = 'F'  

        elif arr[i][j] == 'X':  
            fall.append((i, j))  
            li = i  
            temp = []  
            while li < N and arr[li][j] == 'X':  
                temp.append((li, j))  
                li += 1  

            if arr[li][j] == 'D':  
                for ti, tj in temp:  
                    arr[ti][tj] = 'D'  
            else:  
                for ti, tj in temp:  
                    arr[ti][tj] = [li, j]  

visited = [[INF] * M for _ in range(N)]  

dijkstra(ci, cj)