[Softeer_Python]Lv3. 나무 섭지

문제

https://softeer.ai/practice/7726

 

사용 알고리즘

BFS

 

풀이

고려사항

1. 남우가 갈 수 있는 곳과 유령이 갈 수 있는 곳이 다름

2. 남우와 유령 각각의 탈출구까지 최단거리

 

후기

1. 이 문제는 기본 BFS이지만 2가지 깨달은 점이 있다.

2. 첫번째로 너무 BFS 틀에 갇혀있었다는 점이다.

유령의 경우 가지 못하는 곳이 없으니 탈출구까지 굳이 BFS가 아닌 좌표 차(abs)를 활용하면 무척 간단한 점을 놓쳤다.

이렇게되면, 유령이 많거나 N, M이 크더라도 상관없는 문제였다.

3. 유령이 없을 수도 있는데 무조건 있다는 가정하에 풀이를 진행하였다.

이전 문제 아파트에서도 주어진 조건이 아닌 나의 틀에 박혀 진행했던 적이 있었다.

가장 기본이 되는 예외를 계속 놓치고 있다고 생각들었다.

 

4. 이 문제에 대한 나의 풀이 기본 흐름은 남우와 유령 함께 진행이 아니라

탈출구까지 최단거리를 구하여 비교하여 남우가 유령들보다 짧은 시간 내에 도착할 수 있는지 확인하였다.

 

5. 첫 풀이는 시간초과가 발생했다.

해당 풀이의 흐름은 남우의 bfs를 탐색 후 남우가 탈출구까지 갈 수 있다면

for문을 돌며 유령을 차례로 각!각! bfs를 진행하였다.

이때, for - else를 사용하여 중간에 남우보다 짧은 유령이 있다면 break를 걸어 확인하는 방법을 사용하였다.

이 방법은 예제 21개 중 8개에서 시간초과가 발생하였다.

 

6. 이후 시간초과를 해결하기 위해 유령들을 한번에 BFS를 진행하였다.

진행 횟수가 적은 순으로 q에 들어가고 FIFO 특성을 사용하여 진행하기 때문에

방문여부만 확인해준다면 함께 진행해도 무방하였다.

이때, 4문제 정도가 계속 오답이 나왔는데 이는 유령이 없을 때를 고려하지 않아서이다.

나중에 탈출구까지의 거리를 확인하기 때문에 유령이 없을 경우 1e9로 큰 값을 return하도록 변경하여 해결하였다.

def ghost(g):
    # 방문 확인을 위한 리스트 생성
    visited = [[0] * M for _ in range(N)]

    for g_i, g_j in g:
        visited[g_i][g_j] = 1
    
    while g:
        ci, cj = g.popleft()
        
        for di, dj in didj:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < N and 0 <= nj < M and visited[ni][nj] == 0:
                visited[ni][nj] = visited[ci][cj] + 1
                g.append((ni, nj))

                # 탈출구 도착
                if ni == exit_i and nj == exit_j:
                    return visited[ni][nj]

    return 1e9

 

7. 시간초과를 고려하는 중간에 해당 문제에서 유령은 꼭 BFS를 사용하지 않아도 된다는 사실을 깨달았다.

abs를 사용하면 코드도 깔끔해지고 시간도 엄청 단축된다.

너무 틀에 박혀있었다는 아쉬움이 남는다.

def ghost(g):
    ghost_cnt = 1e9
    for g_i, g_j in g:
        ghost_cnt = min(ghost_cnt, abs(exit_i - g_i) + abs(exit_j - g_j))
    return ghost_cnt + 1

 

 

코드

import sys
from collections import deque
import copy

didj = [[1, 0], [0, 1], [-1, 0], [0, -1]]

# BFS를 활용한 출구찾기
def namwoo(p):
    # 방문 확인을 위한 리스트 생성
    visited = copy.deepcopy(maze)
    p_i, p_j = p[0]
    visited[p_i][p_j] = 1

    while p:
        ci, cj = p.popleft()

        for di, dj in didj:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < N and 0 <= nj < M and visited[ni][nj] == 0:
                visited[ni][nj] = visited[ci][cj] + 1
                p.append((ni, nj))

                # 탈출구 도착
                if ni == exit_i and nj == exit_j:
                    return visited[ni][nj]
                    
    return False


# def ghost(g):
#     # 방문 확인을 위한 리스트 생성
#     visited = [[0] * M for _ in range(N)]

#     for g_i, g_j in g:
#         visited[g_i][g_j] = 1
    
#     while g:
#         ci, cj = g.popleft()
        
#         for di, dj in didj:
#             ni, nj = ci + di, cj + dj
#             if 0 <= ni < N and 0 <= nj < M and visited[ni][nj] == 0:
#                 visited[ni][nj] = visited[ci][cj] + 1
#                 g.append((ni, nj))

#                 # 탈출구 도착
#                 if ni == exit_i and nj == exit_j:
#                     return visited[ni][nj]

#     return 1e9

def ghost(g):
    ghost_cnt = 1e9
    for g_i, g_j in g:
        ghost_cnt = min(ghost_cnt, abs(exit_i - g_i) + abs(exit_j - g_j))
    return ghost_cnt + 1
    


N, M = map(int, input().split())
arr = [list(input()) for _ in range(N)]

# 탈출 위치, 남우와 귀신의 초기 위치 리스트, 미로 재구성
exit_i, exit_j = 0, 0
p, g = deque([]), deque([])
maze = [[0] * M for _ in range(N)]
for i in range(N):
    for j in range(M):
        if arr[i][j] == 'N':
            p.append((i, j))
        elif arr[i][j] == 'G':
            g.append((i, j))
        elif arr[i][j] == '#':
            maze[i][j] = -1
        elif arr[i][j] == 'D':
            exit_i, exit_j = i, j

namwoo_cnt = namwoo(p)   
if namwoo_cnt:
    ghost_cnt = ghost(g)
    if namwoo_cnt >= ghost_cnt:
        print('No')
    else:
        print('Yes')
else:
    print('No')

 

결과