TIL(6일차)

TIL은 6일차지만 여기서는 2주 넘게 지나서 몸이 만신창이 이다 ㅎ....

 

대략적으로 그래프에 대해서 가까워 지는 시간을 가졌는데 오늘은 2문제 푸느라 하루가 다갔다.

 

CSAPP도 읽는데 한 세월이기도 했고......

 

 

https://www.acmicpc.net/problem/3055

3055번: 탈출

 

 

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

---

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

---

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

---

예제 입력 1 

3 3
D.*
...
.S.

예제 출력 1 

3

---

예제 입력 2 

3 3
D.*
...
..S

예제 출력 2 

KAKTUS

---

예제 입력 3 

3 6
D...*.
.X.X..
....S.

예제 출력 3 

6

---

예제 입력 4 

5 4
.D.*
....
..X.
S.*.
....

 

예제 출력 4 

 

4

 

 

 

Approach 

구현 문제 이므로

 

1. 물은 상하좌우로 움직인다.

2. 고슴도치는 물이 있는곳으로 움직일 수 없다.

3. 고슴도치는 상하좌우로 움직인다.

4. 나머지는 예외로 처리해준다 ex) 돌, 비버굴, 범위 초과등

 

위와 같은 로직으로 움직이기 때문에

 

물에 우선순위를 두고 구현을 하였다.

 

다소 더러울 수 있지만 코드는 다음과 같다.

 

---

 

CODE

 

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())

graph = []

visited = [[0]*(m) for _ in range(n)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(n):
  st = list(map(str,input().rstrip()))
  graph.append(st)


def bfs():
    q = deque()

    for i in range(n):
        for j in range(m):
        # 물 부터 큐에 넣어서 움직이게 한다.
            if graph[i][j] == "*":
                q.appendleft((i, j))
                visited[i][j] = 1
           # 그다음 고슴도치
            elif graph[i][j] == "S":
                q.append((i, j))
                visited[i][j] = 1

    while q:
        x, y = q.popleft()

		# 상하좌우 로직
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            # 범위 안에서만 움직이게 만들기
            if 0 <= nx < n and 0 <= ny < m:
            
            # 예외 상황이 발생하면 continue
              if (visited[nx][ny] != 0) or (graph[nx][ny] == "*" or graph[nx][ny] == "X") or (graph[nx][ny] == "D" and graph[x][y] == "*"):
                continue
            # 도착하면 걸린 시간 출력
              if graph[nx][ny] == "D" and graph[x][y] == "S":
                 return visited[x][y]
            # 큐에 들어가고 
              q.append((nx, ny))
            # 걸린 비용 갱신
              visited[nx][ny] = visited[x][y] + 1
            # 판 갱신
              graph[nx][ny] = graph[x][y]
    # 탈출하지 못하면 출력
    return "KAKTUS"


print(bfs())

 

 

if 문이 너무 더러워져 조금 나눠야하나 싶었지만 같은 예외 상황이라 그냥 묶었다....ㅋㅋㅋ