5 분 소요

불

불

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이 난 공간
  • J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3

문제 해석

«««< HEAD

  • 어떠한 수 a 가 리스트 안에 있다면, a를 제외한 나머지 두 수의 합이 a인 수를 좋은 수라고 한다. 그 수의 합을 구하는 것이다.
  • 보통 흔히 생각하는 방법이 2중 루프를 돌면서 각 리스트들과 비교해보는 것인데, 그렇게 되면 비교하는 리스트까지 루프를 돌아야 되서 O(n^3)이 된다. 입력 값 크기는 2000개이므로 O(n^3)이 나오게 되면 시간초과가 뜬다.
  • 두번째 방식이 two pointer 방식이다.
  • 포인터를 2개를 놓고 각자 움직이면서 비교해주는 것이다.
  • 주의해야 할 점은 two pointer 알고리즘은 정렬되어 있는 리스트에서만 이용이 가능하다.

풀이

  • two pointer 알고리즘을 사용하기 위해 lst를 sort() 해준다.
  • 리스트 원소 탐색 루프
    • 자신을 제외한 나머지 두 수의 합이 자신과 맞아야 하기 때문에 자신을 제외한 배열을 temp 라는 배열로 다시 선언
    • left는 index 0부터 시작, end는 temp 리스트의 끝 index에서 시작.
    • left나 right가 서로 역전하는 순간 루프가 꺼지게끔 설계
      • a = left 값 + right 값
      • 만약 a == lst[i]
        • count += 1
        • break
        • break를 하는 이유는 예를 들어 5라는 숫자를 두 수의 합으로 찾아야 한다고 하자
        • 그렇다면 (1,4), (2,3)이 있게 된다.
        • 하지만 5라는 좋은수는 한개이다.
        • 그런데 count는 2개가 올라가기 때문에 1개를 찾는순간 break를 해줘야한다.
      • 만약 a > lst[i]
        • 찾으려는 수보다 커지기 때문에 더해주는 값 두개 중 하나가 작아져야 한다.
        • 작아지는 방법은 end index가 줄어드는 수 밖에 없다
        • 왜냐면 정렬되어 있기 때문이다.
        • end -= 1
      • 만약 a < lst[i]
        • 정렬되어 있기 때문에 합한 숫자를 올리려면 left 값을 올려야 한다.
        • left -= 1
import sys

N = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
lst.sort()

count = 0

for i in range(len(lst)):
    temp = lst[ : i] + lst[i + 1 : ]
    left = 0
    right = len(temp) - 1
    while left < right:
        a = temp[left] + temp[right]
        if lst[i] == a:
            count += 1
            break
        elif lst[i] > a:
            left += 1
        else:
            right -= 1
=======
- 불과 지훈이가 동시에 이동을 하는 것이다.
- 주의할 점은 불은 무조건 4방향 상,하,좌,우로 1시간마다 확산을 하는데, 지훈이는 상,하,좌,우 중 한가지로 이동을 하는 것이다. 
- 지훈이가 확산을 하는 것이 아니다.
- 그래서 지훈이가 한곳씩 이동할 때마다 불은 4곳으로 확산해주는 곳을 생각해야 한다.
- 불이 먼저 확산을 해야 지훈이가 불로 막혀있는곳을 가지 못하게 된다.
- 만약 지훈이가 먼저 이동을 하고 불을 확산시키면 지훈이는 원래 갈 수 없는 길을 갈 수 있게 된다.
- 그리고 지훈이가 2곳을 갈 수 있고, 불이 3곳으로 확산을 하는 경우도 있다.
- 둘이 같은 시간안에 이동을 해야 하므로 count 변수를 queue_fire와 queue_jihun에 넣어주어 count가 같을때만 불을 먼저 전부 확산시키고 지훈이가 이동 시키는 식으로 설계를 해야 한다.
    
# 풀이

- 불이 방문하는 것과 지훈이가 방문하는 것을 고려해야 한다.
- 미로 리스트를 받으면서 지훈이가 나오면 지훈이의 좌표를 저장해주고 방문을 1로 바꾸어준다.
- 불이 나오면 불의 좌표를 넣어주고 방문을 1로 바꾸어준다.
- 여기서 불은 1개도 안나올 수도 있고 여러개가 나올 수도 있으므로 2차원 배열에 append를 해주어야 한다.
- 벽이 있는 곳은 지훈이와 불 둘다 가지 못하기 때문에 둘다 1로 바꾸어준다.
- 지훈 큐와 불 큐에 각 좌표와 count를 넣어준다.
- 불은 여러개가 나올 수도 있으니 갯수만큼 큐에 넣어준다.
- 지훈이 큐가 빌때까지 루프
    - 불 큐가 빌때까지 루프
        - 우리는 무조건 불이 먼저 확산하고 나서 지훈이를 이동시켜야 하기 때문에 지훈이와 불이 같은 count를 가진다면 같은 시간에 확산을 하고 있다는 것이다.
        - 그래서 불이 지훈이와 같은 count를 가진 것들을 전부 먼저 확산 시킨다.
    - 불을 전부 확산시켰다면 지훈이가 갈 수 있는 경로들을 전부 큐에 넣어준다.
    - 불이 있는 곳과 벽이 있는곳, 지훈이가 이미 방문했던 곳은 제외하고 넣어야 한다.
    - 만약 index를 벗어난다면 지훈이는 미로에서 탈출한 것이기 때문에 return 해준다.
- 만약 큐가 빌때까지 돌렸는데 return이 안되었다면 결국 탈출을 못한것이기 때문에 0을 return해준다.

```python
import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

visit_fire = [[0] * C for _ in range(R)]
visit_jihun = [[0] * C for _ in range(R)] 


maze = [[0] * C] * R

for i in range(R):
    maze[i] = list(sys.stdin.readline().rstrip())
fire = []
for i in range(R):
    for j in range(C):
        if maze[i][j] == "J":
            jihun = [i, j]
            visit_jihun[i][j] = 1
        elif maze[i][j] == "F":
            fire.append([i, j])
            visit_fire[i][j] = 1
        elif maze[i][j] == "#":
            visit_jihun[i][j] = 1
            visit_fire[i][j] = 1

queue_jihun = deque()
queue_fire = deque()
queue_jihun.append([jihun[0], jihun[1], 0])
for i in range(len(fire)):
    queue_fire.append([fire[i][0], fire[i][1], 0])


def bfs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue_jihun:
        while queue_fire:
            if queue_jihun[0][2] == queue_fire[0][2]:
                fire_x, fire_y, fire_count = queue_fire.popleft()
                for i in range(4):
                    fire_nx = fire_x + dx[i]
                    fire_ny = fire_y + dy[i]
                    if 0 <= fire_nx < R and 0 <= fire_ny < C and visit_fire[fire_nx][fire_ny] == 0:
                        queue_fire.append([fire_nx, fire_ny, fire_count + 1])
                        visit_fire[fire_nx][fire_ny] = 1
            else:
                break
        jihun_x, jihun_y, jihun_count = queue_jihun.popleft()
        for i in range(4):
            jihun_nx = jihun_x + dx[i]
            jihun_ny = jihun_y + dy[i]
            if jihun_nx < 0 or jihun_nx >= R or jihun_ny >= C or jihun_ny < 0:
                return jihun_count + 1
            elif visit_jihun[jihun_nx][jihun_ny] != 1 and visit_fire[jihun_nx][jihun_ny] != 1:
                queue_jihun.append([jihun_nx, jihun_ny, jihun_count + 1])
                visit_jihun[jihun_nx][jihun_ny] = 1
    return 0

count = bfs()
if count == 0:
    print("IMPOSSIBLE")
else:
    print(count)
>>>>>>> 544699bb1097ad9d7d6e3e82f9dac370fabea426

print(count)

고찰

«««< HEAD

  • two pointer 알고리즘을 처음 알게 되었다.
  • 알고 나면 문제를 쉽게 풀 수 있으나, 이 알고리즘을 생각해내는데 꽤 어렵다.

  • 나중에 two pointer 알고리즘을 이용하는 문제를 3개 정도 더 풀어봐야겠다.

  • 여기서 중요하게 생각할 조건이 불이 먼저 확산하는 것과 같은 count를 가질때에 불을 먼저 전부 확산시켜놓고 지훈이를 움직여야 한다는 것이다.
  • 초기 조건만 잘 생각해놓고 설계를 한다면 큰 어려움이 없다.

    544699bb1097ad9d7d6e3e82f9dac370fabea426

댓글남기기

참고