[CodeTree/Python] n x m 표 이동 5

문제

n x m 표 이동 5

n x m 표에서 (1,1)부터 (n,m)까지 이동하려 할 때 최소한으로 이동할 때 거쳐간 칸의 수를 구하는 프로그램을 작성해보세요.

단, 각 칸에는 0또는 1의 값이 주어져 있고, 1의 값이 주어진 칸 위로만 움질일 수 있습니다.

 

입력 형식

첫 번째 줄에는 n과 m이 주어집니다.

두 번째 줄부터 n개의 줄에 걸쳐 0또는 1이 m개씩 공백을 두고 주어집니다. (1, 1)과 (n, m)은 반드시 1로 주어집니다.

• 2 ≤ n, m ≤ 100

출력 형식

(1, 1)에서 (n, m)까지 최소한의 횟수로 이동할 때 그 횟수를 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

해결

from collections import deque
n, m = map(int, input().split())

# 맵, 방문 리스트 생성
graph = []
visit = []

graph.append([0]*(m+2))
for _ in range(n):
    graph.append([0]+list(map(int, input().split()))+[0])
graph.append([0]*(m+2))

# BFS 큐 생성(deque 사용)
def bfs(x, y):
    Q = deque()
    Q.append((x, y, 1))
    count = 0
    
    dx = [-1, 0, 1, 0] # 북쪽부터 시계방향
    dy = [0, 1, 0, -1]
    
    # 방문 리스트 초기화
    for _ in range(n+2):
        visit.append([False] * (m+2))

    # 현재 노드가 1이고, 아직 방문하지 않았을 시 방문 처리
    if graph[x][y] == 1 and visit[x][y] == False:
        visit[x][y] = True

    while Q:
        (x, y, count) = Q.popleft() # 방문 노드 처리(큐로 처리하기 위해 왼쪽에서부터 꺼냄)

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (1 <= nx <= n) and (1 <= ny <= m):
                if graph[nx][ny] == 1 and not visit[nx][ny]:
                    if nx == n and ny == m:
                        return count + 1
                    visit[nx][ny] == True
                    Q.append((nx, ny, count + 1))

print(bfs(1,1))

 

    BFS(너비 우선 탐색) 알고리즘 문제이므로 deque 자료 형식을 사용하여 풀이하였다. 코드 작성 시 다음을 고려하며 작성하였다.

1. 맵을 받아오는 과정에서 상하좌우로 1칸씩 확장하였다. 따로 이유는 없고 지난 번에 배운 것 복습 겸 연습 겸 해봤다..
   이탈 처리를 해줄 때 사용하려나 했는데 전혀 사용하지 않았다.(^^=)
2. 각 방향에 대한 처리 방식을 변경하였다. 원래 (dx, dy) 좌표 전체로 리스트를 받아와서 반복문을 돌렸는데, 스터디 후 dx, dy에 대한 상하좌우 각 방향으로의 처리만 해서 반복문의 양을 줄여보려고 했다.
3. 특정 노드에 대한 최단 거리 측정 문제이므로, 이동 횟수 카운트를 deque에서 함께 관리하였다.
4. 인접 노드의 값이 1이고, 아직 방문 처리가 되지 않은 경우 방문 처리를 하고 deque에 넣는다.
   특정 노드(n, m)에 도달 시, 마지막으로 카운트를 1회 증가하고 리턴한다. 
   
   

개인적인 궁금증 해소

    처음에는 이동 횟수 카운트 값을 deque의 원소로 함께 관리하지 않고, 전역변수를 설정해서 집계하였다. 이 경우 반복문을 돌면서 count 초기화가 제때 안 되는 건지, 각 노드들을 방문하고 그 노드까지의 이동 횟수 카운트의 값이 모두 누적되는 것 같았다.

    그래서 큐에서 관리하지 않고 이동 횟수 리스트를 따로 생성하는 방법도 괜찮을 것 같아서 고민했다. 내가 코드 짜기는 싫어서 챗gpt한테 코드 주고 위 방식으로 수정해달라고 해봤다(..) 근데 코드트리 테스트 결과는 메모리 초과 했던 것 같다.

 

다음은 챗gpt 답변 결과다.

 

    BFS(너비 우선 탐색) 알고리즘에서 큐를 사용할 때 이동 횟수를 큐에 저장하는 이유는 각 경로의 이동 거리를 정확하게 추적하기 위해서입니다. BFS는 최단 경로를 찾는 데 유리한 알고리즘으로, 각 단계에서 모든 인접 노드를 방문하므로 이동 횟수를 큐에서 관리하면 각 노드에 도달할 때의 정확한 이동 거리를 쉽게 계산할 수 있습니다.

카운트를 큐에서 해주지 않는 경우에도 동작하도록 코드를 수정할 수 있지만, 이는 코드의 가독성과 논리적인 명확성을 떨어뜨릴 수 있습니다. 그러나 만약 카운트를 큐에서 하지 않는 방식으로 구현하고 싶다면, 아래와 같이 할 수 있습니다: --> 혼났다 ㅋㅋㅋㅋ

1. 각 노드에 도달할 때마다 현재까지의 이동 거리를 별도의 리스트로 관리합니다.
2. (n, m)에 도달했을 때의 이동 거리를 반환합니다.

다음은 카운트를 큐에서 관리하지 않는 방식으로 수정한 코드입니다:

from collections import deque

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

# 인접 리스트 생성
graph = []

graph.append([0]*(m+2))
for _ in range(n):
    graph.append([0]+list(map(int, input().split()))+[0])
graph.append([0]*(m+2))

# BFS 큐 생성(deque 사용)
def bfs(x, y):
    Q = deque()
    Q.append((x, y))
    
    dx = [-1, 0, 1, 0]  # 북쪽부터 시계방향
    dy = [0, 1, 0, -1]
    
    # 방문 리스트 초기화
    visit = [[False] * (m + 2) for _ in range(n + 2)]
    distance = [[0] * (m + 2) for _ in range(n + 2)]
    
    # 현재 노드가 1이고, 아직 방문하지 않았을 시 방문 처리
    visit[x][y] = True
    distance[x][y] = 1  # 시작 위치의 거리 초기화

    while Q:
        x, y = Q.popleft()  # 현재 위치

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 1 <= nx <= n and 1 <= ny <= m:  # 경계 내에 있는지 확인
                if graph[nx][ny] == 1 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    distance[nx][ny] = distance[x][y] + 1
                    Q.append((nx, ny))

                    if nx == n and ny == m:  # 목적지에 도달한 경우
                        return distance[nx][ny]

    return -1  # 목적지에 도달할 수 없는 경우 -1 반환 (필요에 따라 수정 가능)

print(bfs(1, 1))

 

수정 사항:

1. distance 리스트를 사용하여 각 노드에 도달할 때의 이동 거리를 저장합니다.
2. 큐에 단순히 위치 (x, y)만 저장하고, 이동 거리는 distance 리스트에서 관리합니다.
3. 목적지 (n, m)에 도달했을 때 distance[n][m]을 반환합니다.

이렇게 하면 이동 횟수를 큐에서 관리하지 않더라도 문제를 해결할 수 있습니다.