[Softeer/소프티어] 나무 섭지 (Lv3 / BFS) - Python

링크

https://softeer.ai/practice/7726/history?questionType=ALGORITHM

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

 

 

문제 해석

지도 상에 나타나는 정보 : 남우, 출구, 유령, 빈공간, 벽
. : 빈칸
D : 탈출구
G : 귀신
# : 벽
N : 남우

 

1초에 한 칸씩 상하좌우로 이동
유령은 벽을 통과할 수 있음
유령은 자기 자리에서 움직이지 않을 수 있음
남우가 유령과 마주치면 잡힘 (출구 자리라도)

 

입력
첫 번째 줄 : n, m  
  n : 행
  m : 열
나머지 줄 : 행렬 정보

 

출력
탈출 가능하면 Yes
탈출 불가능하면 No

 

 

 

 

풀이 & 코드 해석

BFS로 풀 수 있는 턴제형 미로 문제입니다.

 

 

문제에서 명시가 되어 있는 것은 아니지만 매 턴마다 남우가 먼저 움직이고 난 후 나머지 귀신이 움직이는 순서로 되어 있습니다.

 

이에 맞춰 처음 queue에 남우와 귀신 정보를 저장할 때 남우를 먼저 넣고나서 귀신 정보를 넣도록 구현하였습니다. 

 

 

일반적으로 백준 등에 존재하는 미로 문제들과 다른 점은 귀신이 벽을 통과할 수 있다는 점이고, 귀신이 멈춰설 수 있다는 점인데,

이를 해결하기 위해서 남우의 방문처리(nv)와 귀신의 방문처리(gv)를 별도로 진행하였습니다. 

 

 

 

코드

import sys
from collections import deque


def print_arr(arrs):
    for i in range(len(arrs)):
        for j in range(len(arrs[0])):
            print(arrs[i][j], end=" ")
        print()


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

def bfs():
    global n, m, q, ans, nv, gv

    while len(q) != 0:
        px, py, pc = q.popleft()

        for d in range(4):
            nx = dx[d] + px
            ny = dy[d] + py

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 남우일 때
            if pc == 'N':
                if nv[nx][ny] == True or gv[nx][ny] == True or arr[nx][ny] == '#':
                    continue

                # 탈출구를 만나면
                if arr[nx][ny] == 'D':
                    ans = 'Yes'
                    return
                
                nv[nx][ny] = True
                q.append([nx, ny, pc])

            # 유령일 때
            elif pc == 'G':
                if gv[nx][ny] == True:
                    continue
                gv[nx][ny] = True
                q.append([nx, ny, pc])

n, m = list(map(int, input().split()))

arr = []

for _ in range(n):
    arr.append(list(map(str, input().strip())))

other = []

q = deque()
nv = [[False] * m for _ in range(n)]
gv = [[False] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if arr[i][j] == 'N':
            q.append([i, j, 'N'])
            nv[i][j] = True
        elif arr[i][j] == 'G':
            other.append([i, j, 'G'])
            gv[i][j] = True

q.extend(other)

ans = 'No'
bfs()

print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java