[BOJ] 4179 - 불 !

김우경·2021년 1월 27일
0

알고리즘

목록 보기
54/69

문제 링크

불!

문제 설명

R*C 크기의 미로가 주어진다. 미로의 각 칸은 빈칸이거나 지훈이가 위치하거나 불이 위치하거나 벽이 위치한다. 지훈이는 매초 수평/수직 방향으로 이동이 가능하고, 불은 매초마다 네 방향으로 확산된다. 지훈이가 불에 타기 전에 탈출이 가능한지, 가능하다면 얼마나 빨리 탈출 가능한지 구하시오 !

문제 풀이

시도 1

i초에 불이 확산된 위치를 알아야한다. maze에 직접 값을 조작하면 복잡해질 것같아서 fire 리스트를 만들어서 불의 좌표를 저장했다.
fire[i]: i초 뒤에 확산된 불의 좌표들 저장
bfs를 돌면서 t초에서의 지훈이의 이동을 수행하는데

  1. 우선 불을 확산시킨다 (t+1초의 결과)
  2. 지훈이가 이동가능한 네 방향중 벽이 아니고, 불이 확산되지 않은 칸을 queue에 넣어준다.

근데 7%에서 시간초과가 났다 ^_ㅠ,,

import sys
from collections import deque
import copy

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

R, C = map(int, input().split())
maze = []
jihoon = []
fire = [[]]

for i in range(R):
    tmp = list(input().strip())
    for j in range(C):
        if tmp[j] == 'J':
            jihoon = [i,j]
            tmp[j] = '.'
        elif tmp[j] == 'F':
            fire[0].append((i,j))
            tmp[j] = '.'
    maze.append(tmp)

def in_range(x, y):
    if x in range(R) and y in range(C):
        return True
    return False

def move_fire():
    tmp = set()
    for x, y in fire[-1]:
        for i in range(4):
            fx, fy = x+dx[i], y+dy[i]
            if in_range(fx, fy) and maze[fx][fy] != '#':
                tmp.add((fx, fy))
            tmp.add((x, y))
    fire.append(list(tmp))

def bfs(x, y):
    queue = deque([[x, y, 0]])
    visited = [[0]*C for _ in range(R)]
    visited[x][y] = 1

    while queue:
        x, y, time = queue.popleft()

        if x == 0 or x == R-1 or y == 0 or y == C-1:
            return time+1
        
        if len(fire) == time+1:
            move_fire()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny) and visited[nx][ny] == 0 and maze[nx][ny] == '.' and (nx, ny) not in fire[time+1]:
                queue.append([nx, ny, time+1])
                visited[nx][ny] = 1
    return -1

answer = bfs(jihoon[0], jihoon[1])
if answer == -1:
    print("IMPOSSIBLE")
else:
    print(answer)

시도 2

불queue와 지훈이queue를 만들어서 bfs를 각각에 대해서 돌려준다.
while문의 기준을 지훈이로 잡고,

  1. 불을 확산시킨다
  2. 지훈이를 이동시킨다.
    -> 네방향중 빈칸에 있으면 queue에 넣어준다.

이동시의 for문을 for _ in range(len(jihoon)): 로 돌리면 t초에서의 이동만 계산되므로 따로 시간을 저장할 필요가 없다 .

def bfs():
    time = 0
    while jihoon:
        #불 확산시키기
        for _ in range(len(fire)):
            x, y = fire.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and (maze[nx][ny] == '.' or maze[nx][ny] == 'J') :
                    maze[nx][ny] = 'F'
                    fire.append((nx,ny))

        #지훈이 이동
        for _ in range(len(jihoon)):
            x, y = jihoon.popleft()
            if x == 0 or x == R-1 or y == 0 or y == C-1:
                return time+1
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and maze[nx][ny] == '.':
                    maze[nx][ny] = 'J'
                    jihoon.append((nx, ny))
        time += 1
    return -1

전체 코드

import sys
from collections import deque
import copy

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

R, C = map(int, input().split())
maze = []
jihoon = deque()
fire = deque()

for i in range(R):
    tmp = list(input().strip())
    for j in range(C):
        if tmp[j] == 'J':
            jihoon.append((i,j))
        elif tmp[j] == 'F':
            fire.append((i,j))
    maze.append(tmp)

def in_range(x, y):
    if x in range(R) and y in range(C):
        return True
    return False

# fire[i] : i초 뒤 불의 확산좌표들 저장
def move_fire():
    tmp = set()
    for x, y in fire[-1]:
        for i in range(4):
            fx, fy = x+dx[i], y+dy[i]
            if in_range(fx, fy) and maze[fx][fy] != '#':
                tmp.add((fx, fy))
            tmp.add((x, y))
    fire.append(list(tmp))

def bfs():
    time = 0
    while jihoon:
        #불 확산시키기
        for _ in range(len(fire)):
            x, y = fire.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and (maze[nx][ny] == '.' or maze[nx][ny] == 'J') :
                    maze[nx][ny] = 'F'
                    fire.append((nx,ny))

        #지훈이 이동
        for _ in range(len(jihoon)):
            x, y = jihoon.popleft()
            if x == 0 or x == R-1 or y == 0 or y == C-1:
                return time+1
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and maze[nx][ny] == '.':
                    maze[nx][ny] = 'J'
                    jihoon.append((nx, ny))
        time += 1
    return -1

answer = bfs()
if answer == -1:
    print("IMPOSSIBLE")
else:
    print(answer)

느낀점

그동안 bfs를 이용한 문제는 내가 정한 템플릿에 끼워맞춰서 풀었는데 문제에 따라 유동적으로 변경해서 풀 수 있어야될 것 같다. ,,,, 이렇게 큐를 두개 만든다던가,,, 시간을 저장하지 않고 해당 시간내의 가능한 이동을 한번에 처리한다던가 ,,

어렵꾼

profile
Hongik CE

0개의 댓글