[백준 4179번] 불

박형진·2022년 11월 28일
0

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


1. 코드(pypy3, 미완성코드)

import sys
from collections import deque, defaultdict

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

r, c = map(int, sys.stdin.readline().rstrip().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
graph_cnt = [[9999] * c for _ in range(r)]
start_pos = deque()
fire_pos = deque()



for i in range(r):
    for j in range(c):
        if graph[i][j] == 'J':
            start_pos.append((i, j))
        elif graph[i][j] == 'F':
            graph_cnt[i][j] = 0
            fire_pos.append((i, j))

# fire check
while fire_pos:
    x, y = fire_pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] == '#':
                continue
            if graph_cnt[nx][ny] > graph_cnt[x][y] + 1:
                graph_cnt[nx][ny] = graph_cnt[x][y] + 1
                fire_pos.append((nx, ny))

result = defaultdict(int)
for i in range(c):
    if graph[0][i] != '#' and graph_cnt[0][i] != 9999:
        result[(0, i)] = graph_cnt[0][i]
    if graph[r-1][i] != '#' and graph_cnt[r-1][i] != 9999:
        result[(r-1, i)] = graph_cnt[r-1][i]

for i in range(r):
    if graph[i][0] != '#' and graph_cnt[i][0] != 9999:
        result[(i, 0)] = graph_cnt[i][0]
    if graph[i][c-1] != '#' and graph_cnt[i][c-1] != 9999:
        result[(i, c-1)] = graph_cnt[i][c-1]


for i in range(r):
    for j in range(c):
        if graph_cnt[i][j] != 9999:
            graph_cnt[i][j] = 9999
graph_cnt[start_pos[0][0]][start_pos[0][1]] = 0
while start_pos:
    x, y = start_pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] == '#':
                continue
            if graph_cnt[nx][ny] > graph_cnt[x][y] + 1:
                graph_cnt[nx][ny] = graph_cnt[x][y] + 1
                start_pos.append((nx, ny))
if not result:
    ans = []
    no_fire_result = defaultdict(int)
    for i in range(c):
        if graph[0][i] != '#' and graph_cnt[0][i] != 9999:
            no_fire_result[(0, i)] = graph_cnt[0][i]
        if graph[r - 1][i] != '#' and graph_cnt[r - 1][i] != 9999:
            no_fire_result[(r - 1, i)] = graph_cnt[r - 1][i]

    for i in range(r):
        if graph[i][0] != '#' and graph_cnt[i][0] != 9999:
            no_fire_result[(i, 0)] = graph_cnt[i][0]
        if graph[i][c - 1] != '#' and graph_cnt[i][c - 1] != 9999:
            no_fire_result[(i, c - 1)] = graph_cnt[i][c - 1]

    for pos in no_fire_result:
        ans.append(no_fire_result[pos]+1)
    if not ans:
        print('IMPOSSIBLE')
    else:
        print(sorted(ans)[0])
else:
    ans = []
    for pos in result:
        x, y = pos
        fire = result[pos]
        j = graph_cnt[x][y]
        if j < fire:
            ans.append(j + 1)
    if not ans:
        print('IMPOSSIBLE')
    else:
        print(sorted(ans)[0])

일단 답만 맞아보려고 급하게 코드를 작성했음. 시간초과 나지 않는 코드 완성되면 수정 예정

2. 완성 코드

import sys
from collections import deque


def fire_move():
    while fire_q:
        x, y = fire_q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c:
                if graph[nx][ny] == '#':
                    continue
                if fire[nx][ny] > fire[x][y] + 1 and not fire_v[nx][ny]:
                    fire_v[nx][ny] = True
                    fire[nx][ny] = fire[x][y] + 1
                    fire_q.append((nx, ny))


def jay_move():
    while jay_q:
        x, y = jay_q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not 0 <= nx < r or not 0 <= ny < c:
                print(jay[x][y] + 1)
                return
            if 0 <= nx < r and 0 <= ny < c:
                if graph[nx][ny] == '#' or graph[nx][ny] == 'F':
                    continue
                if fire[nx][ny] > jay[x][y] + 1 and not jay_v[nx][ny]:
                    jay_v[nx][ny] = True
                    jay[nx][ny] = jay[x][y] + 1
                    jay_q.append((nx, ny))
    print('IMPOSSIBLE')
    return


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = float('inf')

r, c = map(int, sys.stdin.readline().rstrip().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
fire = [[INF] * c for _ in range(r)]
jay = [[INF] * c for _ in range(r)]
fire_v = [[False] * c for _ in range(r)]
jay_v = [[False] * c for _ in range(r)]
fire_q = deque()
jay_q = deque()

for i in range(r):
    for j in range(c):
        if graph[i][j] == 'J':
            jay_q.append((i, j))
            jay[i][j] = 0
        elif graph[i][j] == 'F':
            fire_q.append((i, j))
            fire[i][j] = 0

fire_move()
jay_move()

방문 여부를 저장하는 2차원 배열을 선언해야 메모리 초과가 발생하지 않는다.

profile
안녕하세요!

0개의 댓글