BOJ - 공주님을 구해라! 17839번 (python)

❓ 문제 - 백준 공주님을 구해라 ! 17839번 - python 풀이법

출처 

(https://www.acmicpc.net/problem/17836)

17836번: 공주님을 구해라!

 

 

 

📝 문제해결법

1. 이 문제는 그래프탐색(BFS)로 풀었다.

• 방문처리를 위해 visited 리스트를 선언하여, 해당 노드를 방문했을 때 이미 접근한 노드라면 최소 비용이 아니므로 방문하지 않았을 때 queue에 append 처리
• 4방향으로 탐색하면서 리스트 범위 안에, 방문하지 않은 노드에서 만약 벽이라면 continue, 빈공간이라면 방문 처리 후 queue 에 append
• 무기 습득 시, 방문처리해주고 무기를 습득하면 queue를 통해 4방향을 탐색할 필요가 없이 공주가 있는 위치와 현 위치의 차이만을 계산하면 시간을 계산할 수 있으므로 queue에 append 하지 않아도 됨
• 차이를 계산해서, 주어진 시간보다 시간이 작다면 시간을 갱신
• queue를 다 돌면서 공주가 있는 위치에 오면 현재 걸린 시간과 최소 시간을 최솟값 비교를 통해 갱신
• 만약 queue를 돌면서 주어진 시간(공주에 도달해야하는) 보다 길다면 queue를 도는 것을 종료

 

💻 소스코드

# 공주님을 구해라 ! - BOJ 17836
# BFS
from collections import deque

n, m, t = map(int, input().split())
visited = [[0 for _ in range(m)] for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
gonju = 10001

def bfs(a, b):
    global gonju
    q = deque()
    q.append((a, b, 0))
    visited[a][b] = 1

    while q:
        x, y, time = q.popleft()
        if x == n-1 and y == m-1:
            gonju = min(gonju, time)
            break
        if time+1 > t:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny]==0:
                if graph[nx][ny] == 1:
                    continue
                elif graph[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny, time+1))
                else:
                    visited[nx][ny] = 1
                    diff = time + 1 + abs(nx-(n-1)) + abs(ny-(m-1))
                    if diff <= t:
                        gonju = diff

bfs(0, 0)

if gonju > t:
    print('Fail')
else:
    print(gonju)

 

 

 

2. 문제를 위해 해결하는 과정(try...)

 1) 테스트케이스는 통과했지만 문제가 틀림

-> 무기를 얻었을 경우 상태를 변화해서 벽을 통과할 수 있게 했는데 이게 queue에서 무기를 얻지 못했을 경우도 상태가 변화되어 벽을 통과 가능해짐 

 

import sys
from collections import deque

input = sys.stdin.readline


n, m, t = map(int, input().split())
visited = [[10001] * m for _ in range(n)]

graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(a, b):
    q = deque()
    weapon = False
    q.append((a, b))
    visited[a][b] = 0

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if weapon:
                    if visited[nx][ny] > visited[x][y] + 1:
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny))
                else:
                    if graph[nx][ny] == 1:
                        continue
                    elif graph[nx][ny] == 2:
                        weapon = True
                    if visited[nx][ny] > visited[x][y] + 1:
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny))

bfs(0, 0)
if visited[n-1][m-1] > t:
    print('Fail')
else:
    print(visited[n-1][m-1])

 

 

2) 메모리 초과로 틀림

-> 이게 모든 행과 열을 다 방문하기 때문에 queue에 들어가는 데이터가 많아져서 메모리 초과가 발생

->  방문처리(visited)의 기능을 살려서 방문된 경우는 방문하지 않도록 코드를 수정해야함

from collections import deque

n, m, t = map(int, input().split())
visited = [[10000] * m for _ in range(n)]


graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(a, b):
    q = deque()
    q.append((a, b, 0))
    visited[a][b] = 0

    while q:
        x, y, w = q.popleft()
        if x == n-1 and y == m-1:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if w == 1:
                    if visited[nx][ny] >= visited[x][y] + 1:
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny, 1))
                else:
                    if graph[nx][ny] == 1:
                        continue
                    elif graph[nx][ny] == 2:
                        w = 1

                    if visited[nx][ny] > visited[x][y] + 1:
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny, w))


bfs(0, 0)

if visited[n-1][m-1] > t:
    print('Fail')
else:
    print(visited[n-1][m-1])