백준 2178번 - 미로 탐색

Posted on | In , , | Comments:

코테 풀이들은 대부분 길어서 더보기 클릭을 하지 않으면 보이지 않도록 해당 문구를 추가합니다.

백준 2178: 미로 탐색

문제 출처 : https://www.acmicpc.net/problem/2178

image

문제 설명

출발 지점과 도착 지점이 주어진 최단 거리 구하기 문제 이다.
한 지점을 기준으로 BFS를 차근차근 수행해가며 값을 누적시키면 문제를 해결할 수 있다.
최단 거리 문제가 나오면 일단 BFS를 떠올려 보자!

문제 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
[풀이 논리]
1. 시작점이 (1,1)이고 도착점이 (N,M)이므로, 한칸씩 당겨서 시작점을 (0,0) 도착점을 (N-1,M-1)로 설정한다.
2. visited라는 리스트를 만들고 주어진 graph와 dim을 맞춰서 0을 넣어놓는다.
3. 시작점에서 시작해서 bfs를 수행하고, 해당 지점이 도착점과 같아질 때 함수를 종료한다.
4. 지점을 방문할때마다 visited의 값을 누적시킨다.

def bfs():
    # 상하좌우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque([start]) # (0,0)을 q에 넣고
    visited[start[0]][start[1]] = 1 # 방문 처리

    while queue:
        x, y = queue.popleft()

        if x == end[0] and y == end[1]: # 종료 조건
            return visited[x][y]

        for i in range(4): # 상하좌우로 인접 탐색
            next_x, next_y = x + dx[i], y + dy[i]

            if valid(next_x, next_y): # 좌표가 유효한 경우,
                queue.append([next_x, next_y]) # 해당 좌표를 큐에 넣고
                visited[next_x][next_y] = visited[x][y] + 1 # 방문처리하여 값 누적


def valid(x,y):
    if 0 <= x < N and 0 <= y < M: # 범위에서 벗어나지 않고,
        if graph[x][y] == 1 and visited[x][y] == 0: # 길이 있고, 방문한 적이 없다면
            return True
    return False


if __name__ == "__main__":
    import sys; readline = sys.stdin.readline
    from collections import deque
    N, M = map(int, readline().split())
    graph = []
    for _ in range(N):
        _list = [int(i) for i in readline().strip()]
        graph.append(_list)

    start = [0, 0] # (1,1)이 처음이므로 1칸씩 뒤로 당김
    end = [N-1, M-1]
    visited = [[0] * M for _ in range(N)] # 0으로 초기화
    print(bfs())

풀이 포인트
최단 거리 구하기 문제는 BFS 떠올리기
값 누적시킬 visited 리스트를 새로 만들기
내가 실수했던 부분 : visited 리스트 만들 때 리스트 구조를 이상하게 만들었었음 ㅠ
얌전하게 [[0] * M for _ in range(N)] 이런식으로 합시다..
아니면 걍 [[0 for _ in range(M)] for _ in range(N)] 이렇게 적던가