[softeer] 나무섭지 BFS python 문제풀이

소프티어 문제 Lv. 3 나무 섭지, 나 무섭지?

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

 

 

💡 문제의 핵심

• 남우(N)가 유령(G)을 피해 출구(D)로 탈출할 수 있는지를 판별해야 합니다.
• 유령은 벽을 통과할 수 있고 먼저 움직이며, 남우는 벽을 통과할 수 없습니다.
• 남우가 출구에 유령보다 먼저 도착하면 "Yes", 그렇지 않으면 "No"를 출력해야 합니다.

 

🚀 코드 설명

1️⃣ 입력을 읽고, 격자(grid) 정보를 저장

n, m = map(int, input().split())  # 격자의 크기 (n x m)
grid = [input().strip() for _ in range(n)]  # 격자 정보 저장

➡ n x m 크기의 격자를 입력받고 저장

예를 들어, 입력이 다음과 같다면:

5 5
#####
#N..#
#.#G#
#...#
#D###

 

• # → 벽
• N → 남우의 위치
• G → 유령의 위치
• D → 출구

2️⃣ 남우와 유령의 위치 찾기

namu_pos = None
exit_pos = None
ghosts = []

for i in range(n):
    for j in range(m):
        if grid[i][j] == 'N':
            namu_pos = (i, j)  # 남우 위치 저장
        elif grid[i][j] == 'D':
            exit_pos = (i, j)  # 출구 위치 저장
        elif grid[i][j] == 'G':
            ghosts.append((i, j))  # 유령 위치 저장

 

➡ 격자에서 남우(N), 유령(G), 출구(D)의 위치를 찾아 저장

 

3️⃣ BFS 함수 (bfs)

from collections import deque

dx = [-1, 1, 0, 0]  # 상하좌우 이동 (X축 방향)
dy = [0, 0, -1, 1]  # 상하좌우 이동 (Y축 방향)

def bfs(start_points, grid, n, m, is_ghost):
    queue = deque(start_points)  # 시작 위치들을 큐에 추가
    time = [[float('inf')] * m for _ in range(n)]  # 도달 시간을 무한대로 초기화
    
    for x, y in start_points:
        time[x][y] = 0  # 시작 위치의 시간은 0
    
    while queue:
        x, y = queue.popleft()  # 현재 위치 꺼내기
        
        for i in range(4):  # 상하좌우 이동
            nx, ny = x + dx[i], y + dy[i]  

            if 0 <= nx < n and 0 <= ny < m:  # 격자 범위 안에 있을 때
                if is_ghost:
                    # 유령은 벽을 통과할 수 있음
                    if time[nx][ny] > time[x][y] + 1:
                        time[nx][ny] = time[x][y] + 1
                        queue.append((nx, ny))
                else:
                    # 남우는 벽을 통과할 수 없음
                    if grid[nx][ny] != '#' and time[nx][ny] > time[x][y] + 1:
                        time[nx][ny] = time[x][y] + 1
                        queue.append((nx, ny))
    
    return time

4️⃣ 유령과 남우의 이동 시간 계산

ghost_time = bfs(ghosts, grid, n, m, is_ghost=True)  # 유령의 도달 시간 계산
namu_time = bfs([namu_pos], grid, n, m, is_ghost=False)  # 남우의 도달 시간 계산

➡ 각 위치에 유령과 남우가 도착하는 최단 시간을 계산

 

5️⃣ 출구에서 비교하고 결과 출력

ex, ey = exit_pos
if namu_time[ex][ey] < ghost_time[ex][ey]:  # 남우가 출구에 유령보다 먼저 도착하면
    print("Yes")
else:
    print("No")

➡ 출구에서 남우가 유령보다 빨리 도착하면 "Yes", 아니면 "No"를 출력

 

🔥 최종 코드 (정리본)

from collections import deque

dx = [-1, 1, 0, 0]  # 상하좌우 이동
dy = [0, 0, -1, 1]

def bfs(start_points, grid, n, m, is_ghost):
    queue = deque(start_points)
    time = [[float('inf')] * m for _ in range(n)]
    
    for x, y in start_points:
        time[x][y] = 0
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m:
                if is_ghost:
                    if time[nx][ny] > time[x][y] + 1:
                        time[nx][ny] = time[x][y] + 1
                        queue.append((nx, ny))
                else:
                    if grid[nx][ny] != '#' and time[nx][ny] > time[x][y] + 1:
                        time[nx][ny] = time[x][y] + 1
                        queue.append((nx, ny))
    
    return time

def can_escape(n, m, grid):
    namu_pos = None
    exit_pos = None
    ghosts = []
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'N':
                namu_pos = (i, j)
            elif grid[i][j] == 'D':
                exit_pos = (i, j)
            elif grid[i][j] == 'G':
                ghosts.append((i, j))
    
    ghost_time = bfs(ghosts, grid, n, m, is_ghost=True)
    namu_time = bfs([namu_pos], grid, n, m, is_ghost=False)
    
    ex, ey = exit_pos
    if namu_time[ex][ey] < ghost_time[ex][ey]:
        return "Yes"
    else:
        return "No"

n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]
print(can_escape(n, m, grid))

💎 정리

1. 입력받아 남우, 유령, 출구 위치 찾기
2. 유령은 0개 이상이므로 리스트로 받기
3. BFS로 유령과 남우의 이동 시간 둘 다 계산
4. 출구에서 남우가 유령보다 빨리 도착하면 "Yes", 아니면 "No" 출력