2178번: 미로 탐색

import sys

floor_max, room_max = map(int, sys.stdin.readline().split())
floor_dic = {}
floor_count_dic = {}

for i in range(1, floor_max + 1):

    floor_input = sys.stdin.readline().strip()

    for j in range(1, room_max + 1):
        if floor_input[j - 1] == "1":
            floor_dic[str(i) + " " + str(j)] = []
            floor_count_dic[str(i) + " " + str(j)] = 0

for floor_room in floor_dic.keys():
    floor, room = map(int, floor_room.split())

    # 오른쪽 방과 관련한 키를 만듭니다.
    if room != room_max:
        right_room = str(floor) + " " + str(room + 1)
        # 옆방이 존재 한다면( 0 이 아니라면 ), 접근 가능한 방으로 현재 방의 값으로 추가 한다.
        if right_room in floor_dic.keys():
            floor_dic[floor_room].append(right_room)

    # 왼쪽 방과 관련한 키를 만듭니다.
    if room != 1:
        left_room = str(floor) + " " + str(room - 1)
        # 옆방이 존재 한다면, 접근 가능한 방으로 현재 방의 값으로 추가 한다.
        if left_room in floor_dic.keys():
            floor_dic[floor_room].append(left_room)

    # 위쪽 층의 방과 관련한 키를 만듭니다.
    if floor != 1:
        up_room = str(floor - 1) + " " + str(room)
        # 아래 층 방이 존재 한다면, 접근 가능한 방으로 현재 방의 값으로 추가 한다.
        if up_room in floor_dic.keys():
            floor_dic[floor_room].append(up_room)

    # 아래쪽 층의 방과 관련한 키를 만듭니다.
    if floor != floor_max:
        down_room = str(floor + 1) + " " + str(room)
        # 아래 층 방이 존재 한다면, 접근 가능한 방으로 현재 방의 값으로 추가 한다.
        if down_room in floor_dic.keys():
            floor_dic[floor_room].append(down_room)

bfs_queue = ["1 1"]
bfs_set = {"1 1"}
floor_count_dic["1 1"] = 1

while True:
    floor_room = bfs_queue.pop(0)

    if floor_room == str(floor_max) + " " + str(room_max):
        break

    for contact_room in floor_dic[floor_room]:
        # 현재 방에 연결된 방 중에 접근한적 없는 방이라면
        if contact_room not in bfs_set:
            floor_count_dic[contact_room] = floor_count_dic[floor_room] + 1
            bfs_set.add(contact_room)
            bfs_queue.append(contact_room)

print(floor_count_dic[str(floor_max) + " " + str(room_max)])

알고리즘(2023.05.11)

• 각 칸에 1과 0을 방이 존재한다. 존재하지 않는다로 구분했다. 층과 방으로 구분했는데 각 층에 각방이 1이라면 방이 존재 한다. 0이라면 존재하지 않는다 라고 생각했다.

• 방이 존재 하는 경우 층(행) + “ ” + 방(열)을 키로 저장했다. 키의 값으로는 리스트를 유동적인 데이터를 저장할 수 있도록 했다.

• 현재 방을 기준으로 끝단에 있는 방이 아니라면 위, 아래, 오른쪽, 왼쪽 방에 접근하여 방이 존재한다면 층 과 방을 현재 방을 키로하는 리스트에 저장했다.

  • 이렇게 되면 각 방은 자신의 방과 연결된 방을 그 값으로 리스트에 저장하고 있는것이다.

• 넓이 우선 탐색을 진행하여 최단 거리를 찾기로 하였다. 최단 거리를 찾는 방법으로는 각 키에 해당하는 값으로 정수형 값을 가지게 되는데 첫번째 방은 그 값이 1, 첫번째 방과 연결된 방은 2 이처럼 현재방과 연결된 방은 현재 방이 가지고 있는 값의 + 1값을 가지게 된다.

  Breadth-First Search, BFS

• 넓이 우선 탐색은 큐 자료형을 사용하여 구현되었으며, 무한 반복을 통해 실행되면 무한 반복이 끝나는 조건은 현재방이 목적지의 방과 동일하면 끝나게 된다.