본문 바로가기
Algorithm/Graph

[파이썬] 백준 4179, 5427 : 불!, 불 (골드4)

by 베짱이28호 2023. 5. 29.

[파이썬] 백준 4179, 5427 : 불!, 불 (골드4)

 

 

4179번: 불!

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

www.acmicpc.net

문제

# 엣지케이스

# test case 2% : 탈출구 주변에 불이 존재하는 경우
# 5 5
# #F..#
# #.J.#
# ###.#
# ###.#
# ###.#

# test case 80?% : 시작하자마자 탈출할 수 있는 경우
# 3 3
# .JF
# ...
# ...

풀이

0. 방향성 생각

최단거리를 탐색하는 BFS 문제.

사람 탐색을 우선으로 하기, 하지만 가장자리에 도달했을 경우 주변에 불이 있는지 탐색하는 과정이 필요

 

1. 입력 받기, 시작 위치, 불 위치 찾기

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(input()))
    
fire = []
for i in range(h):
    for j in range(w):
        if arr[i][j] == 'F' :
            fire.append((j,i))
        if arr[i][j] == 'J' :
            a,b = j,i

시작 위치는 하나라서 a,b로 받기.

불 위치는 0개 이상이라서 리스트로 받기.

 

2. BFS 함수 구현

# 1)
step = [[1,-1,0,0],[0,0,1,-1]]
visit_f = [[-1]*w for i in range(h)]
visit = [[-1]*w for i in range(h)]

# 2)
def bfs():   
    q = deque()
    visit[b][a] = 0
    q.append((a,b,0))
    
    for i in fire :
        x,y = i
        visit_f[y][x] = 0
        q.append((x,y,1))

    while q :     
        x,y,f = q.popleft()     
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            # 3)
            if f==0 :
                if 0<=nx<w and 0<=ny<h and visit[ny][nx] == -1 :
                    if arr[ny][nx] == '.' and visit_f[ny][nx] == -1 :
                        visit[ny][nx] = visit[y][x] + 1
                        q.append((nx,ny,0))
                        
                        if nx==0 or nx==w-1 or ny==0 or ny==h-1:
                            escape = True
                            for i in range(4):
                                nnx = nx + step[0][i]
                                nny = ny + step[1][i]
                                if 0<=nnx<w and 0<=nny<h :
                                    if visit_f[nny][nnx] != -1 or arr[nny][nnx] == 'F':
                                        escape = False
                                        break
                            if escape == True:
                                return visit[ny][nx]+1
            # 4)                    
            else :
                if 0<=nx<w and 0<=ny<h and visit_f[ny][nx] == -1 :
                    if arr[ny][nx] == '.' or arr[ny][nx] == 'J' :
                        if visit[ny][nx] >= visit_f[ny][nx]:
                            visit_f[ny][nx] = visit_f[y][x] + 1
                            q.append((nx,ny,1))
                        
    return 'IMPOSSIBLE'
  1. 사람이 탐색하는 리스트 visit, 불이 탐색하는 리스트 visit_f, 4가지 방향 정의
  2. 큐에 시작 위치, 불 위치를 추가한다. 큐에서 사람, 불을 구분하기 위해 좌표 뒤에 0,1로 사람 불을 구분한다.
  3. 사람이 탐색하는 경우 : 범위 내에 있고  탐색하지 않은 좌표 탐색. 걸린 시간을 갱신하고 큐에 추가한다. 가장자리에 도달했을 경우 escape 변수를 True로 만들고 가장자리 주변을 한 번 더 탐색한다. 주변에 불이 탐색한 경우에 False로 만들고 루프 탈출. 그렇지 않은 경우에는 탈출 가능하므로 좌표를 얻어온다.
  4. 불이 탐색하는 경우 : 범위 내에 있고 탐색하지 않은 좌표 탐색. 통로 또는 시작위치일 경우 불이 지나간 시간 갱신하고 큐에 추가.
  5. 모든 루프가 끝났음에도 불구하고 탈출하지 못할경우 IMPOSSIBLE

3. 출력

if a==0 or a==w-1 or b==0 or b==h-1:
    print(1)
else : 
    answer = bfs()
    print(answer)

탈출지점이 벽에 없는 경우에만 함수 실행

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(input()))
    
fire = []
for i in range(h):
    for j in range(w):
        if arr[i][j] == 'F' :
            fire.append((j,i))
        if arr[i][j] == 'J' :
            a,b = j,i

step = [[1,-1,0,0],[0,0,1,-1]]
visit_f = [[-1]*w for i in range(h)]
visit = [[-1]*w for i in range(h)]

def bfs(): 
    
    q = deque()
    visit[b][a] = 0
    q.append((a,b,0))
    
    for i in fire :
        x,y = i
        visit_f[y][x] = 0
        q.append((x,y,1))

    while q :
        
        x,y,f = q.popleft()
        
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]

            if f==0 :
                if 0<=nx<w and 0<=ny<h and visit[ny][nx] == -1 :
                    if arr[ny][nx] == '.' and visit_f[ny][nx] == -1 :
                        visit[ny][nx] = visit[y][x] + 1
                        q.append((nx,ny,0))
                        
                        if nx==0 or nx==w-1 or ny==0 or ny==h-1:
                            escape = True
                            for i in range(4):
                                nnx = nx + step[0][i]
                                nny = ny + step[1][i]
                                if 0<=nnx<w and 0<=nny<h :
                                    if visit_f[nny][nnx] != -1 or arr[nny][nnx] == 'F':
                                        escape = False
                                        break
                            if escape == True:
                                return visit[ny][nx]+1
            else :
                if 0<=nx<w and 0<=ny<h and visit_f[ny][nx] == -1 :
                    if arr[ny][nx] == '.' or arr[ny][nx] == 'J' :
                        if visit[ny][nx] >= visit_f[ny][nx]:
                            visit_f[ny][nx] = visit_f[y][x] + 1
                            q.append((nx,ny,1))
                        
    return 'IMPOSSIBLE'

if a==0 or a==w-1 or b==0 or b==h-1:
    print(1)
else : 
    answer = bfs()
    print(answer)

엣지케이스 고려를 잘 해야겠다..

엣지케이스 2개 말고는 빨리 풀었는데 두개 생각하고 구현하느라 시간 좀 오래 썼다.

탈출 3055에 조건이 더 달려있어서 더 까다로운 문제.

(다른 사람 풀이 시간, 메모리를 보면 효율적으로 짠 코드는 아님)

 

같은 방법으로 푼 5427번

from collections import deque
import sys
input = sys.stdin.readline

def bfs():    
    q = deque()
    visit[b][a] = 0
    q.append((a,b,0))
    for i in fire :
        x,y = i
        visit_f[y][x] = 0
        q.append((x,y,1))

    while q :    
        x,y,f = q.popleft()      
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]

            if f==0 :
                if 0<=nx<w and 0<=ny<h and visit[ny][nx] == -1 :
                    if arr[ny][nx] == '.' and visit_f[ny][nx] == -1 :
                        visit[ny][nx] = visit[y][x] + 1
                        q.append((nx,ny,0))
                        
                        if nx==0 or nx==w-1 or ny==0 or ny==h-1:
                            escape = True
                            for i in range(4):
                                nnx = nx + step[0][i]
                                nny = ny + step[1][i]
                                if 0<=nnx<w and 0<=nny<h :
                                    if visit_f[nny][nnx] != -1 or arr[nny][nnx] == '*':
                                        escape = False
                                        break
                            if escape == True:
                                return visit[ny][nx]+1
            else :
                if 0<=nx<w and 0<=ny<h and visit_f[ny][nx] == -1 :
                    if arr[ny][nx] == '.' or arr[ny][nx] == '@' :
                        if visit[ny][nx] >= visit_f[ny][nx]:
                            visit_f[ny][nx] = visit_f[y][x] + 1
                            q.append((nx,ny,1))                      
    return 'IMPOSSIBLE'

t = int(input())
for i in range(t):
    w,h = map(int,input().split())
    arr = []
    for i in range(h):
        arr.append(list(input()))
        
    fire = []
    for i in range(h):
        for j in range(w):
            if arr[i][j] == '*' :
                fire.append((j,i))
            if arr[i][j] == '@' :
                a,b = j,i
    
    step = [[1,-1,0,0],[0,0,1,-1]]
    visit_f = [[-1]*w for i in range(h)]
    visit = [[-1]*w for i in range(h)]

    if a==0 or a==w-1 or b==0 or b==h-1:
        print(1)
    else : 
        answer = bfs()
        print(answer)

'Algorithm > Graph' 카테고리의 다른 글

[파이썬] 백준 1260 : DFS와 BFS (실버2)  (0) 2023.06.03
[파이썬] 백준 16928 : 뱀과 사다리 게임 (골드5)  (0) 2023.06.03
[파이썬] 백준 11403 : 경로 찾기 (실버1)  (0) 2023.06.02
[파이썬] 백준 3055 : 탈출 (골드4)  (0) 2023.05.25
[파이썬] 백준 5014 : 스타트링크 (실버1)  (0) 2023.05.24
[파이썬] 백준 12851, 13913 : 숨바꼭질 2, 숨바꼭질 4 (골드4)  (0) 2023.05.23
[파이썬] 백준 13549 : 숨바꼭질 3 (골드5)  (2) 2023.05.22

관련글

댓글

티스토리툴바