[백준] 2178번 - 미로탐색

실버 1 - https://www.acmicpc.net/problem/2178

Code

from collections import deque

# 입력 받기
N, M = map(int, input().split())
matrix = list(list(map(int, input())) for _ in range(N))

visited = [list(0 for _ in range(M)) for _ in range(N)]     # 방문 체크용 배열
ans = [list(0 for _ in range(M)) for _ in range(N)]         # 방문 순서 확인용 배열

q = deque()     # 큐 선언

# 이동 가능한 좌표인지 확인하는 함수
def can_go(x, y):
    if(x < 0 or y < 0 or x >= N or y >= M):
        return False
    if(matrix[x][y] == 0 or visited[x][y] == 1):
        return False
    else:
        return True

# # (0,0) 시작
q.append((0, 0, 1))
visited[0][0] = 1
ans[0][0] = 1

# 방향 설정
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# BFS 탐색
while(q):
    curr_point = q.popleft()    # 현재 위치

    x = curr_point[0]
    y = curr_point[1]
    curr_move_cnt = curr_point[2]       # 현재 이동한 횟수

    ans[x][y] = curr_move_cnt       # 큐에서 꺼낸 (x, y) 이동 가능하므로 담겼기 때문에 방문 순서 확인을 위해 ans배열에 이동 횟수 넣어주기

    # 상하좌우 탐색
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]

        # 이동 가능하다면 -> 현재 이동한 횟수+1 을 해서 큐에 해당 좌표 담아주기, 재탐색하지 않도록 방문 처리
        if(can_go(new_x, new_y)):
            q.append((new_x, new_y, curr_move_cnt+1))
            visited[new_x][new_y] = 1

# 방문 순서 확인을 위한 출력
for i in range(len(ans)):
    print(ans[i])

# 정답 출력
print(ans[N-1][M-1])

풀이 및 해설

• 큐를 통해서 BFS 순회하며 (1, 1)을 시작으로 도착지점인 (N, M)까지의 최단거리 찾기 → 보통 최단거리 문제는 BFS로 푼다고 한다 ! ! ! (BFS는 현재가 항상 최적 경로임을 보장)
  
• 처음에는 move_cnt 값을 이동 가능한 좌표를 발견할 때마다 +1 되도록 큐 밖에서 더해줬는데, 그렇게 되면 최단이동횟수를 찾기 어려워짐 → 따라서 큐에 좌표와 함께 넣어주며 꺼낼 때 변수로 지정해서 저장해두며 갱신하기

• 현재 좌표에서 상하좌우를 둘러보며 찾은 이동 가능한 좌표 → 큐에 삽입
• 이동 가능한 좌표의 최단거리 == 현재 move_cnt에 +1된 값
  → 이걸 함께 큐의 요소로 넣어주기

What I learned

▶️ 파이썬의 DFS, BFS
참고 자료 : https://11001.tistory.com/77

• 가중치가 없는 최단 경로 : BFS 사용하기
  • DFS : 특정 칸에 처음 도달했을 때까지의 경로 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장못함.
  • BFS : 특정 칸에 처음 도달했을 때까지의 경로 길이가 항상 최적임을 보장
• DFS는 스텍 터질 위험이 커서 BFS 사용하는게 나을 수도 있음
• 최대 길이를 구하는 문제는 BFS 가 유리하다는 의견이 많음
• 백트래킹은 DFS 알고리즘의 하위 분류
  • DFS(재귀)를 수행하여 타고타고 깊게 들어가다가 특정 조건을 만나면 탐색 중단하고 되돌아간다. 그 과정에서 원하는 해를 찾는 알고리즘이다.

▶️ 붙어서 입력되는 문자열을 띄워서 리스트로 저장하는 방법
참고 자료 : https://bio-info.tistory.com/29

• list() 함수 이용하기
  • list() 함수에 문자열을 넣으면 한 문자씩 다 나누어 리스트를 생성함
    (공백도 한 문자로 취급)

입력 : 
101111
101010
101011
111011

matrix = [list(map(int, input())) for _ in range(N)]

---

matrix 출력:
[[1, 1, 0, 1, 1, 0], [1, 1, 0, 1, 1, 0], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 1]]

→ 기존 2차원 배열을 입력받는 코드에서 input() 뒤에 .split()만 제거하면 list() 함수에 의해서 자동으로 쪼개짐