[오늘의 문제]
https://www.acmicpc.net/problem/4179
[오늘의 학습 키워드]
- BFS
1. 문제 설명
지훈이가 미로에서 탈출하려고 합니다.
미로에 탈출구는 가장자리에 접한 공간으로 탈출이 가능합니다.
미로에는 불이 났고 지훈이가 미로에서 불타기 전에 탈출할 수 있다면 탈출에 걸린 시간을,
탈출이 불가능한 경우 IMPOSSIBLE을 출력하는 문제입니다.
지훈이와 불은 대각선으로 이동할 수 없습니다. 즉 delta 4방향으로만 이동이 가능하다는 의미입니다.
[제한사항]
- 시간 제한 1초
- 메모리 제한 256MB
- 1 ≤ R, C ≤ 1000
- # 벽
- . 지훈이가 이동 가능한 공간
- J 지훈이의 초기 위치
- F 불이 난 공간
- J 는 입력에서 하나만 주어집니다.
2. 접근 방식
여기서 주의할 점은 J는 입력에서 하나만 주어진다는 것입니다.
이 말은 F 즉, 불은 미로에서 동시에 여러 공간에서 발생 가능하다는 소리입니다.
그럼 불이 난 공간을 처리할 visited 배열을 생성하여 불이난 곳을 모두 체크해 주어야 하겠죠
그리고 불이 붙기 까지 걸린 시간을 visited 배열에 업데이트 하는데
지훈이가 불이 붙기 전에 해당 공간으로 이동이 가능하면 이동하고
그렇지 않은 경우 이동을 하지 않습니다.
즉 불을 먼저 미로에 다 지른 뒤 시간에 따라서 지훈이가 탈출이 가능한지 확인하면 될 것 같습니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque
# 입력
R, C = map(int, input().split())
maze = [list(map(str, input())) for _ in range(R)]
# 델타 탐색 4방향
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 미로에 불지르기
def fire():
queue = deque()
# 미로에 불은 동시다발적으로 발생이 가능하니 불이난 위치를 기준으로 최소값으로 초기화 해주어야 동시에 불을 지를 수 있다.
# 따라서 visited를 최대값으로 초기화
visited = [[float('inf')] * C for _ in range(R)]
# 불이난 위치 queue에 넣기
for i in range(R):
for j in range(C):
if maze[i][j] == 'F':
queue.append((i, j))
visited[i][j] = 0
# 동시다발적으로 불 지르기 시작
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 불은 미로안에만 발생
if 0 <= nx < R and 0 <= ny < C:
# 다음 이동위치가 벽만 아니라면 모든 위치에 불을 지를 수 있다.
if maze[nx][ny] != '#' and visited[nx][ny] == float('inf'):
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))
return visited
def BFS(x, y, visited):
# 지훈이의 중복이동을 방지할 check 배열
check = [[False] * C for _ in range(R)]
check[x][y] = True
queue = deque([(x, y, 0)]) # 시작위치 x, 시작위치 y, 이동시간
while queue:
x, y, move = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 미로의 범위를 벗어나지 않은 경우
if 0 <= nx < R and 0 <= ny < C:
# 지훈이가 이동 가능하고, 이동한 적이 없고, 불이 아직 안난 곳 찾기
if maze[nx][ny] == '.' and not check[nx][ny] and move + 1 < visited[nx][ny]:
check[nx][ny] = True
queue.append((nx, ny, move + 1))
# 미로를 벗어나는 경우 -> 탈출이 가능한 경우
elif not (0 <= nx < R and 0 <= ny < C):
return move + 1
# BFS 탐색으로 탈출이 불가능한 경우
return "IMPOSSIBLE"
# 미로에 불 먼저 지르기
visited = fire()
for i in range(R):
for j in range(C):
# 지훈이 위치 찾고 BFS 탐색하여 탈출 가능여부 확인하기
if maze[i][j] == 'J':
answer = BFS(i, j, visited)
print(answer)
exit()[코드 설명]
# 미로에 불지르기
def fire():
queue = deque()
# 미로에 불은 동시다발적으로 발생이 가능하니 불이난 위치를 기준으로 최소값으로 초기화 해주어야 동시에 불을 지를 수 있다.
# 따라서 visited를 최대값으로 초기화
visited = [[float('inf')] * C for _ in range(R)]
# 불이난 위치 queue에 넣기
for i in range(R):
for j in range(C):
if maze[i][j] == 'F':
queue.append((i, j))
visited[i][j] = 0
# 동시다발적으로 불 지르기 시작
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 불은 미로안에만 발생
if 0 <= nx < R and 0 <= ny < C:
# 다음 이동위치가 벽만 아니라면 모든 위치에 불을 지를 수 있다.
if maze[nx][ny] != '#' and visited[nx][ny] == float('inf'):
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))
return visited
미로에 불을 질러 줍니다.
불을 지를 위치는 실제 maze에 하면 안되니 maze의 넓이를 가지는 visited 배열을 생성해 주었고
불은 여러 위치에서 동시에 발생 가능하므로 모든 불의 위치를 찾아서 queue에 넣어줍니다.
또한 불이 동시에 발생 한다면 현재 위치에서 다음 위치로 불이 발생하는 경우 해당 위치의 이동시간이 더 적어야 동시에 불이 발생한 경우 입니다.
따라서 visited 배열을 최대값으로 생성해 주었고, 불은 미로 안에만 발생 하니 불의 이동위치를 제한해 주었습니다.
또 불은 벽만 아니라면 발생 가능합니다.
이때 다음 이동위치는 불이 안난 곳에만 나야겠죠
BFS 탐색할 때 queue에 모든 시작위치를 넣고 popleft로 뽑기 때문에 순서에 맞춰 불이 발생합니다.
# 미로에 불 먼저 지르기
visited = fire()
for i in range(R):
for j in range(C):
# 지훈이 위치 찾고 BFS 탐색하여 탈출 가능여부 확인하기
if maze[i][j] == 'J':
answer = BFS(i, j, visited)
print(answer)
exit()
앞서 불을 질러 생성한 visited 배열을 기준으로 지훈이의 위치를 찾아서 BFS 탐색을 실시합니다.
J는 하나만 주어지기 때문에 정답을 출력하고 바로 종료합니다.
def BFS(x, y, visited):
# 지훈이의 중복이동을 방지할 check 배열
check = [[False] * C for _ in range(R)]
check[x][y] = True
queue = deque([(x, y, 0)]) # 시작위치 x, 시작위치 y, 이동시간
while queue:
x, y, move = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 미로의 범위를 벗어나지 않은 경우
if 0 <= nx < R and 0 <= ny < C:
# 지훈이가 이동 가능하고, 이동한 적이 없고, 불이 아직 안난 곳 찾기
if maze[nx][ny] == '.' and not check[nx][ny] and move + 1 < visited[nx][ny]:
check[nx][ny] = True
queue.append((nx, ny, move + 1))
# 미로를 벗어나는 경우 -> 탈출이 가능한 경우
elif not (0 <= nx < R and 0 <= ny < C):
return move + 1
# BFS 탐색으로 탈출이 불가능한 경우
return "IMPOSSIBLE"
BFS로 지훈이가 탈출이 가능한지 확인해 줍니다.
이때 지훈이가 미로안에서 영원히 돌지 않도록 check 배열을 생성하여 중복 탐색을 방지해 줍니다.
지훈이의 시작위치와 이동시간을 queue에 넣고 탈출이 가능한지 탐색을 실시합니다.
지훈이의 다음 이동위치가 미로를 벗어나지 않는 경우 즉, 길로 이동하는 경우 조건이 필요합니다.
1. 다음 이동위치가 .으로 길이어야 한다.
2. 아직 그 길을 지나간적이 없어야 한다.
3. 해당 길에 불이 아직 나지 않았어야 한다.
모든 조건중 3번 조건을 지키기 위해 move를 만들었습니다.
이동하며 check를 확인하고 이동한 경우 move를 1 늘려 이동해줍니다.
만약 다음 이동위치가 미로를 벗어나는 경우라면 지훈이가 탈출한 것이므로
현재 move 기준으로 이동까지 1초 더 소요되니 1을 추가해 탈출시켜 줍니다.
만약 BFS로 탈출이 불가능한 경우 IMPOSSIBLE을 반환합니다.
4. 결과
[회고]
어제 풀었던 문제보다는 조금 쉬운 문제였습니다.
BFS만 잘 해주면 되는데
저는 BFS를 두번 돌리기로 했습니다.
처음 BFS 탐색을 실시할 때, 불이난 위치를 기준으로 BFS 탐색을 실시하고
한번더 전체 탐색을 실시하여 지훈이의 위치를 찾아주었는데 그렇게 하니 시간초과 났습니다.
두번째는 11%에서 틀렸었는데 반례를 찾아보니 미로에 불이 나지 않는 경우도 있었습니다.
이 경우를 고려하지 않아서 탈출을 시도하여 틀렸었습니다.
미로에 불이 나는 경우 fx, fy를 설정하여 값을 입력하고 불이 나지 않는 경우 -1로 초기화 하여 fire 가 실행 될때 x, y 값이 -1 이라면 visited 배열을 최대값으로 설정하여 반환을 하였는데 다음 경우에도 11% 에서 틀렸습ㄴ다.
그래서 이유를 찾던 중 불이 여러군데에서 발생 가능한 반례를 찾았습니다.
또한 코드를 작성하며
3 5
#####
#J...
F.#..
의 경우가 존재하였는데 여기서 정답은 4가 출력되어야 하는데 계속 2가 출력되었습니다.
그래서 코드를 수정하고 있었는데 불이 번지는 경우를 잘못 설정하였었습니다.
불이 동시에 여러군데에서 발생 가능하니 처음에는 반복문을 통해 불이 나는 모든 경우 fire함수를 실행했는데
이렇게 하면 결국 마지막 위치에서 불이 난 경우만 업데이트 하였습니다.
따라서 마지막 수정으로 불이난 위치를 모두 queue에 넣고 탐색을 돌렸고 그 결과 맞출 수 있었습니다.
쉬운문제였는데 문제에 조건을 제대로 안 읽고 경우의 수를 고려하지 않아서 조금 헤맸지만 재밌게 푼 문제 였습니다.
'알고리즘' 카테고리의 다른 글
| [백준] 20304 - 비밀번호 제작 - 플레 5 (0) | 2025.04.01 |
|---|---|
| [백준] 16987 - 계란으로 계란치기 - 골드 5 (0) | 2025.03.31 |
| [백준] 17471 게리맨더링 - 골드 3 (0) | 2025.03.30 |
| [백준]1662 압축 - 골드 4 (0) | 2025.03.28 |
| [백준] 6539 상범 빌딩 - 골드 5 (0) | 2025.03.23 |