[백준/Python] 14923번(BFS)_미로 탈출

📌문제 유형

BFS

 

📌문제

14923번: 미로 탈출

 

 

📌나의 문제풀이

- 시간초과

• 막고 있는 벽 1개씩 부수며 진행
• 시간복잡도 증가

from collections import deque

n,m = map(int,input().split())
hx,hy = map(int,input().split())
hx,hy = (hx-1),(hy-1)
ex, ey = map(int,input().split())
ex,ey = (ex-1),(ey-1)

maps = []
walls = []
for i in range(n):
    list_ = list(map(int,input().split()))
    maps.append(list_)
    for j in range(len(list_)):
        if maps[i][j] == 1:
            walls.append([i,j])

# 벽 개수만큼
idx, ans = 0, 1000000
while True:
    if idx == len(walls):
        break

    break_x, break_y = walls[idx]
    maps[break_x][break_y] = 0

    q = deque([])
    q.append([hx,hy])
    visited = [[0 for _ in range(m)] for _ in range(n)]
    visited[hx][hy] = 1

    cnt = 0
    while q:
        x,y = q.popleft()
        
        if x == ex and y == ey:
            break

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if maps[nx][ny] == 0 and visited[nx][ny] == 0:
                    q.append([nx,ny])
                    visited[nx][ny] = visited[x][y] + 1


    cnt = visited[ex][ey]
    if ans == 0 and cnt > ans:
        ans = cnt
    elif ans != 0 and cnt < ans:
        ans = cnt
    
    maps[break_x][break_y] = 1
    idx += 1

if ans == 0:
    print(-1)
else:
    print(ans-1)

 

📌다른사람의 문제풀이

- 3차원 visited

• 벽을 부수고 지나간 곳, 벽을 부수지 않고 지나간 곳 나누어서 visited 작성
• 일종의 그리디

from collections import deque

n,m = map(int,input().split())
hx,hy = map(int,input().split())
hx,hy = (hx-1),(hy-1)
ex, ey = map(int,input().split())
ex,ey = (ex-1),(ey-1)

maps = []
for i in range(n):
    list_ = list(map(int,input().split()))
    maps.append(list_)

q = deque([])
q.append([hx,hy,0,1])
visited = [[[0,0] for _ in range(m)] for _ in range(n)]
visited[hx][hy][1] = 1

# 벽을 만났을때 magic== 1 벽 아직 안 뿌숨 
cnt = 0
while q:
    x,y, cnt, magic = q.popleft()
        
    if x == ex and y == ey:
            break

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if visited[nx][ny][magic] == 1:
                continue

            if maps[nx][ny] == 1 and magic == 1:
                visited[nx][ny][0] = 1
                q.append([nx,ny, cnt+1, magic-1])
            elif maps[nx][ny] == 0:
                visited[nx][ny][magic] = 1
                q.append([nx,ny, cnt+1, magic])
                

if cnt == 0:
    print(-1)
else:
    print(cnt)

 

백준 14923번 "미로 탈출" by 파이썬

 

📌리뷰

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

- 경우의 수

1)이동할 곳이 벽, 즉 1이고 현재까지 뚫고 온 벽의 개수가 0인 상황,
2)이동할 곳이 빈칸, 즉 0이고 현재까지 뚫고 온 벽의 개수가 1인 상황,
3)이동할 곳이 빈칸, 즉 0이고 현재까지 뚫고 온 벽의 개수가 0인 상황