[백준] 5427 불 - 골드 4
[오늘의 문제]
https://www.acmicpc.net/problem/5427
[오늘의 학습 키워드]
- 너비 우선 탐색
- 그래프 탐색, 그래프 이론
- 구현
- 격자 그래프
1. 문제설명
상근이는 빌딩에서 탈출하려 합니다.
빌딩의 크기는 각각 N, M 으로 주어지며 상근이의 위치와, 불이 난 곳, 벽, 빈 공간의 정보가 2차원 배열에 담겨 주어집니다.
불이 매 초마다 4방향으로 번지기 시작할 때 상근이가 빌딩에서 탈출이 가능하다면 탈출에 걸린 시간을
탈출이 불가능하다면 IMPOSSIBLE을 반환하는 프로그램을 작성하는 문제 입니다.
[제한사항]
- 시간 제한 1초
- 메모리 제한 256MB
- 테스트 케이스는 최대 100개
- 1 ≤ N, M ≤ 1000
2. 접근방식
저는 우선 빌딩에 불을 모두 지르고 상근이가 탈출이 가능한지를 판별하였습니다.
불도 사방에 번지는데 1초씩 시간이 걸립니다.
즉, 불이 번지기 위해서는 불도 이동시간이 필요하다는 뜻이고 불이 번지기 전에 상근이가 빌딩에서 탈출할 수 있다면 탈출에 걸린
시간을 출력해 주어야 하죠
이를 위해서 몇 가지 고려사항이 있습니다.
1. 불은 한 군데에서만 발생하지 않는다.
2. 불이 번지는 곳은 벽을 제외한 모든 곳에 번질 수 있다.
3. 이미 불이난 곳과 새로 번지게 된 불의 위치가 동일한 경우 시간을 비교하여 더 짧게 걸린 쪽으로 최신화 하야여 한다.
4. 상근이는 빌딩을 탈출하기 위해서 격자 밖으로 이동해야 한다. -> 종료조건
5. 상근이가 이동할 수 있는 곳은 불이 나지 않았거나, 불이 붙기 전인 곳으로만 이동이 가능하다.
위 조건들을 고려하며 코드를 작성해 주어야 합니다.
가장 먼저 중첩 반복문을 이용해 불의 위치와 상근이의 위치를 모두 찾아주어야 합니다.
그리고 불을 빌딩에 질러주어야 하죠
이렇게 하는 이유는 상근이가 먼저 이동하여 빌딩을 탈출하는데 걸린 시간을 토대로 불을 질러가며 경우의 수를 삭제하는 것 보다
먼저 불을 질러놓고 해당 위치로 이동이 가능한지 판별하는게 더 쉽기 때문입니다.
이동이 가능한지 여부는 불이 해당 위치에 붙기 까지 걸린 시간을 토대로, 상근이가 해당 위치까지 이동에 걸린 시간을
서로 비교하여 더 짧게 걸린경우 이동이 가능한 위치인 것이죠
이런식으로 이동이 가능한 곳을 모두 이동하며 탈출구를 찾았을 때, 그때 걸린 시간을 반환하여 주었습니다.
코드로 설명하겠습니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 불 지르기
def FIRE(fire):
# 불은 queue에 저장된 상태 따라서 while로 바로 queue 탐색 시작
while fire:
fx, fy = fire.popleft()
for k in range(4):
nx = fx + dx[k]
ny = fy + dy[k]
# 불은 범위를 벗어나지 않고 빌딩 안에서만 나야한다.
if 0 <= nx < N and 0 <= ny < M:
# 불이 번지는 곳은 벽이 아니고, 가본적이 없거나, 불이 더 빨리 붙어야 하는곳
if buliding[nx][ny] != '#' and (visited[nx][ny] == 0 or visited[nx][ny] > visited[fx][fy] + 1):
fire.append((nx, ny))
visited[nx][ny] = visited[fx][fy] + 1
# 상근이 탈출 시작
def BFS(sx, sy):
queue = deque([(sx, sy)])
visited[sx][sy] = 1 # 상근이 시작위치 초기화 -> 상근이 이동 정보 저장
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 상근이가 이동 가능한 곳
if 0 <= nx < N and 0 <= ny < M:
# 벽이 아니고, 불이 안 붙은 0 혹은 불이 오기전에 이동이 가능한 곳
if buliding[nx][ny] != '#' and (visited[nx][ny] == 0 or visited[nx][ny] > visited[x][y] + 1):
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))
# 종료 조건 -> 상근이가 빌딩 범위 밖으로 탈출이 가능한 곳
if not (0 <= nx < N and 0 <= ny < M):
return visited[x][y]
# 탈출 실패
return "IMPOSSIBLE"
# 입력
T = int(input())
for _ in range(T):
M, N = map(int, input().split())
buliding = [list(map(str, input().strip())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
fire = deque() # 불은 여러 곳에서 날 수 있다.
people_x, people_y = 0, 0 # 상근이 위치는 한 곳만 주어 진다.
for i in range(N):
for j in range(M):
# 불 위치 찾아 저장 & 불 지르기
if buliding[i][j] == '*':
fire.append((i, j))
visited[i][j] = 1
# 상근이 위치 찾기
if buliding[i][j] == '@':
people_x, people_y = i, j
# 불 먼저 지르고, 상근이 탈출 시작
FIRE(fire)
print(BFS(people_x, people_y))[코드설명]
# 입력
T = int(input())
for _ in range(T):
M, N = map(int, input().split())
buliding = [list(map(str, input().strip())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
fire = deque() # 불은 여러 곳에서 날 수 있다.
people_x, people_y = 0, 0 # 상근이 위치는 한 곳만 주어 진다.
for i in range(N):
for j in range(M):
# 불 위치 찾아 저장 & 불 지르기
if buliding[i][j] == '*':
fire.append((i, j))
visited[i][j] = 1
# 상근이 위치 찾기
if buliding[i][j] == '@':
people_x, people_y = i, j
# 불 먼저 지르고, 상근이 탈출 시작
FIRE(fire)
print(BFS(people_x, people_y))
우선 입력을 받아줍니다.
빌딩의 정보는 문자로 주어지며, 공백없이 붙어서 주어집니다.
또 불이 나서 이동하는 곳과 상근이가 이동하는 곳은 같은 공간을 사용하기 때문에 먼저 visited 배열을 생성해 주었습니다.
불이 붙는 곳은 여러곳이고 상근이의 위치는 1곳만 존재하기 때문에 각각의 정보를 따로 저장해 주었습니다.
불의 시작위치는 불이 난 곳마다 달라야 하기 때문에 불의 위치를 찾아 queue에 저장할 때 미리 visited 배열을 초기화 해주었습니다.
이를 토대로 각각의 BFS 탐색을 실시해 주었습니다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 불 지르기
def FIRE(fire):
# 불은 queue에 저장된 상태 따라서 while로 바로 queue 탐색 시작
while fire:
fx, fy = fire.popleft()
for k in range(4):
nx = fx + dx[k]
ny = fy + dy[k]
# 불은 범위를 벗어나지 않고 빌딩 안에서만 나야한다.
if 0 <= nx < N and 0 <= ny < M:
# 불이 번지는 곳은 벽이 아니고, 가본적이 없거나, 불이 더 빨리 붙어야 하는곳
if buliding[nx][ny] != '#' and (visited[nx][ny] == 0 or visited[nx][ny] > visited[fx][fy] + 1):
fire.append((nx, ny))
visited[nx][ny] = visited[fx][fy] + 1
먼저 빌딩에 불을 질러주었습니다.
불의 위치정보는 fire 로 생성된 queue에 저장되어 있습니다.
FIRE 함수를 실행하며 저장된 queue 정보를 그대로 가져와 바로 while문을 돌려 주었습니다.
불의 시작위치를 토대로 4방향 탐색을 실시하는데 불이 번질 수 있는 곳은
1. 벽이 아니어야 합니다.
2. 아직 불이 난적이 없어야 합니다.
3. 또는 불이 난 곳이라도 이번에 번지는 불이 더 빨리 발생하는 불이어야 합니다.
2번과 3번의 조건은 불이 아직 붙지 않았거나 혹은 이미 붙엇어도 지금 붙는 불이 더 빨리 붙는 불이어야 합니다.
즉 이번에 번지게 되는 불이 기존에 발생한 불보다 시간이 더 짧게 걸려야 하니 or 조건으로 묶어 주었고
조건도 기존에 발생한 불의 시간이 더 큰 경우로 구분해 주었습니다.
1 번 조건은 필수 조건이기 때문에 2번 3번 조건을 괄호로 묶어 하나의 경우로 처리하고 and로 엮어 주었습니다.
이렇게 빌딩에 불을 질러 이동 가능한 모든 조건을 구한뒤 불을 모두 질러 주었습니다.
# 상근이 탈출 시작
def BFS(sx, sy):
queue = deque([(sx, sy)])
visited[sx][sy] = 1 # 상근이 시작위치 초기화 -> 상근이 이동 정보 저장
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 상근이가 이동 가능한 곳
if 0 <= nx < N and 0 <= ny < M:
# 벽이 아니고, 불이 안 붙은 0 혹은 불이 오기전에 이동이 가능한 곳
if buliding[nx][ny] != '#' and (visited[nx][ny] == 0 or visited[nx][ny] > visited[x][y] + 1):
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))
# 종료 조건 -> 상근이가 빌딩 범위 밖으로 탈출이 가능한 곳
if not (0 <= nx < N and 0 <= ny < M):
return visited[x][y]
# 탈출 실패
return "IMPOSSIBLE"
빌딩에 모두 불이 붙었다면 상근이의 탈출이 시작되어야 합니다.
상근이의 위치는 1차적으로 항상 불이 붙기 전인 곳입니다.
따라서 상근이의 시작 위치를 1로 초기화 하고 4방향 탐색을 통해 이동 가능한 모든 곳을 찾아 주었습니다.
상근이가 이동 가능한 곳은
1. 벽이 아니어야 합니다.
2. 불이 붙지 않은 곳이어야 합니다.
3. 또는 불이 아직 붙지 않은 곳이어야 합니다.
2번과 3번 조건은 비슷해 보이지만 전혀 다른 조건입니다.
예시로
* # .
* # @
* # #
위 그림처럼 빌딩의 정보가 주어진다면 2번과 3번의 조건은 전혀 다른 조건이 되죠
2번 조건의 경우 불이 완전히 붙지 않는 곳 즉, 벽에 막혀 불이 이동하지 못하는 곳을 의미합니다.
3번 조건의 경우 불이 붙을 수는 있는데 상근이가 먼저 이동하는 곳이 되죠
따라서 두 조건을 동일하게 or 조건으로 묶어 주었고 괄호로 묶어 하나의 조건으로 처리해 주었습니다.
동일하게 1번 조건을 필수 조건이기 때문에 and로 묶어 주었습니다.
상근이가 이동하는 곳은 상근이의 이동 시간보다 불이 늦게 붙는 곳이어야 합니다.
즉, 상근이가 이동하기 전에 이미 불이 붙은 곳은 이동할 수 없겠죠
따라서 상근이의 이동 시간보다 불이 더 늦게 붙은 곳, 현재 위치의 불이 이동 시간이 상근이의 이동 시간보다 커야 합니다.
위 조건을 토대로 상근이가 이동이 가능한 모든 곳을 찾아 queue에 넣어 줍니다.
모든 조건을 토대로 상근이의 이동이 완료되면 상근이가 탈출 할 수 있는지를 찾아주어야 겠죠
이 역시 현재 위치를 기준으로 4방향 탐색을 할때, 빌딩 범위를 벗어나야 하니 for문 속에서 종료 조건을 작성해 주었습니다.
모든 조건을 넘어가서 빌딩을 탈출할 수 없다면 마지막 IMPOSSIBLE이 반환되죠
4. 결과
[회고]
처음 문제를 풀때 생각보다 조건이 어렵지 않아 금방 조건을 세울 수 있었습니다.
그러나 조건을 세워 맞는지 확인하는 과정에서 여러가지 반례가 존재 했습니다.
기존에 작성한 코드는 상근이의 이동조건, 불의 이동조건 등이 완벽하지 않아 다른 결과가 출력되었고 12%에서 틀리더라구요
https://www.acmicpc.net/board/view/151874
여기에 작성된 반례를 하나하나 맞춰가며 조건을 수정하였고 정답을 맞출 수 있었습니다.
이번 문제를 풀며 가장 중요한 점은 BFS를 각각 실행해 주어야 한다는 것입니다.
불이 먼저 붙고 상근이의 이동이 실시 되어야 하니 queue가 다르거나 혹은 사용한 queue를 비워주어야 하죠
또한 상근이의 이동 정보와 불의 이동 정보를 토대로 하나의 visited 배열을 이용해 불을 질러주어야 합니다.
모든 조건이 만족할 때 결과가 제대로 출력되었습니다.
많이 고민한 문제는 아니었지만 재밌게 푼 문제 입니다.