[Python]백준 #2178 미로 탐색 (DFS, BFS)

✔️알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

✔️ 실패한 접근방법

1. DFS 로 탐색. 한 좌표에서 동서남북 모든 길을 재귀호출로 탐색

2. 이동할 때마다 count 를 +1 해주고 만약 길을 되돌아올 경우 count 를 -1 해줌 

3. 풀이는 가능하지만 재귀호출이 너무 많아 시간초과 ( ** 가지치기 시도해보고 싶었으나 진행 X)

from copy import deepcopy
import sys
import queue
#sys.setrecursionlimit(1000000)

class Maze:

    def __init__(self, graph, visited, find_x, find_y):
        self.graph = graph
        self.visited = visited
        self.find_x = find_x
        self.find_y = find_y
        self.count = 0
        self.que = queue.Queue()

    def find_route(self,x,y):
        # 쌓는 순서는 목표지점 (x,y)에 가까운 순서
        # 새로 쌓을 때마다 counting
        # 목표지점 (x,y)가 쌓이면 끝
        self.x = x
        self.y = y
        self.count_flag = 0
        self.succes_flag = 0
        self.que.put([x, y])
        self.visited[x][y] = 1
        #self.count += 1

        while(self.que.empty() == False):
            self.x,self.y = self.que.get()
            self.count += 1
            print(f'{self.x},{self.y}')

            if(self.x == self.find_x and self.y == self.find_y):
                break

            self.go_east(self.x, self.y)
            self.go_west(self.x, self.y)
            self.go_south(self.x, self.y)
            self.go_north(self.x, self.y)

            '''
            if(self.count_flag == 1):
                self.count += 1
            else:
                self.count -= 1

            if(self.succes_flag == 1):
                break

            self.count_flag = 0
            self.x,self.y = self.que.get()
            #self.count += 1
            '''

        print(self.count)
    
    
    def find_route(self,x,y):
        #print(f'x={x},y={y}')
        #print("호출")
        self.visited[x][y] = 1
        if(self.find_y == y and self.find_x == x):
            if(self.count < self.final_count):
                self.final_count = self.count
                self.visited[x][y] = 0
                self.count -= 1
                return 0

        self.go_east(x, y)
        self.go_west(x, y)
        self.go_south(x, y)
        self.go_north(x, y)
        self.visited[x][y] = 0

        self.count -= 1

        #메소드 호출될때마다 count++
        #찾고하는 위치인지 매번 확인
        #도달 방식이 여러개일 수 있기 때문에 if(도달) : 이전 도달 count 랑 비교하여 작으면 갱신 같으면 내비두기 크면 내비두기
        #시작지점부터 동서남북으로 탐색
        #return 될때마다 count --
        # => 재귀허출을 너무 많이 하는 문제 발생 #불필요한 재귀호출 많으면서 시간초과
      
        
    def go_east(self,x, y):
        if(0 <= x <= self.find_x and 0 <= y + 1 <= self.find_y): #길이 존재
            #if(x == self.find_x and y+1 == self.find_y):
            #    self.succes_flag = 1
            #    return 0
            if(self.graph[x][y+1] == 1 and self.visited[x][y+1] == 0): #방문 한 적이 없음
                self.que.put([x,y+1]) # 큐에 추가
                self.visited[x][y+1] = 1
                self.count_flag = 1


        # 동쪽으로 한칸 이동(동쪽이 0이면 그대로 return)
        # 길이 존재하고 방문 x 위치면 해당 위치로 find_route 이동)

    def go_west(self,x, y):
        if (0 <= x <= self.find_x and 0 <= y - 1 <= self.find_y):
            #if (x == self.find_x and y - 1 == self.find_y):
            #    self.succes_flag = 1
            #    return 0
            if(self.graph[x][y-1] == 1 and self.visited[x][y-1] == 0):
                self.que.put([x,y-1])
                self.visited[x][y-1] = 1
                self.count_flag = 1

    def go_south(self,x, y):
        if (0 <= x + 1 <= self.find_x and 0 <= y <= self.find_y):
            #if (x+1 == self.find_x and y == self.find_y):
            #    self.succes_flag = 1
            #    return 0
            if(self.graph[x+1][y] == 1 and self.visited[x+1][y] == 0):
                self.que.put([x+1,y])
                self.visited[x+1][y] = 1
                self.count_flag = 1


    def go_north(self,x, y):
        if(0 <= x - 1 <= self.find_x and 0 <= y <= self.find_y):
            #if (x-1 == self.find_x and y  == self.find_y):
            #    self.succes_flag = 1
            #    return 0
            if(self.graph[x-1][y] == 1 and self.visited[x-1][y] == 0):
                self.que.put([x-1,y])
                self.visited[x-1][y] = 1
                self.count_flag = 1


def main():

    N, M = map(int, input().split())
    graph = [[0 for col in range(M)] for row in range(N)]

    ## 넘파일 배열로 구현
    for i in range(N):
        # str = input()
        str = sys.stdin.readline()
        for j in range(M):
            graph[i][j] = int(str[j])

   
    #visited = graph # 미친 얕은 복사라 graph랑 같은 배열 가르킴....
    #visited = graph.copy() #2차원 이상의 다차원 리스트는 리스트를 완전히 복사하려면 copy 메서드 대신 copy 모듈의 deepcopy 함수를 사용
    visited = deepcopy(graph)
    ## 넘파일 배열로 구현
    for i in range(N):
        #str = input()
        str = sys.stdin.readline()
        for j in range(M):
            graph[i][j] = int(str[j])

    maze = Maze(graph, visited, N-1, M-1)
    maze.find_route(0,0)
    #print(maze.final_count + 1)
   

if __name__ == '__main__':
    main()

 

✔️ 새로운 접근방법

1. BFS 로 탐색. BFS를 사용해 재도전해봤지만 길을 되돌아갈때 count 를 어떻게 더하고 빼줘야 할지 몰라서 실패

2. 좌표에 인접한 모든 길을 한번에 모두 탐색하고 좌표에 있는 값에 +1 을 해준다. (해당 길에 도달하기까지의 최단거리)

   값이 1이 아니면 더이상 접근하지 않기 때문에 값은 항상 최단거리로 설정된다. (** (0,0)은 예외)

3. 동서남북에 접근하기 위해서 dx, dy 리스트를 만들고 반복문을 사용해 조합을 더해주는 방식 사용

import sys
import queue

def main():

    N, M = map(int, input().split())
    graph = []
    for _ in range(N):
        graph.append(list(map(int, input().rstrip()))) # 줄바꿈 문자 제거

    # 상하좌우
    dx = [-1, 1, 0, 0] # 좌표에서 (0,1)은 행렬에서 [1,0] y축이 행, x축이 열
    dy = [0, 0, -1, 1]
    # -> 하상우좌

    def bfs(x, y):
        que = queue.Queue()
        que.put([x,y])
        
        while(not que.empty()): # 큐가 빌때까지 반복
            x,y = que.get()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                #print(f'({nx},{ny})')

                if(0 <= nx < N and 0<= ny <M and graph[nx][ny] == 1):
                    # 해당 좌표에 길이 존재하고 도착지점을 넘지 않는지 확인
                    que.put([nx, ny])
                    graph[nx][ny] = graph[x][y] + 1
                    # 조건절 -> 같은 좌표 2번 이상 지나기 불가능
                    # 해당 좌표에 도달하기 위해 현재까지 이동한 최소 칸수 표시

        return graph[N-1][M-1]

    print(bfs(0,0))
   

if __name__ == '__main__':
    main()

✔️ 배운점/아쉬운점

1. 주로 사용하는 deque 대신에 Queue 모듈을 사용해보았고, 원소 추가/삭제가 더 용이하다고 느꼈다. 

2. deque 는 while(deque) 로 사용하지만 Queue 는 while(not Queue .empty()) / while(Queue .empty() == 0)  사용

 ** while(Queue .empty() == False) 는 TypeError 발생 (여기서 너무 애먹었다,,,,)

3. 동서남북에 접근하는 방법을 함수호출하는 것이 아니라 행렬(리스트) 조합으로 더욱 간단하게 해결

4. 시작할 때부터 인접한 좌표에 값을 바꿔주기 때문에 각 좌표는 항상 최단거리로 지정되는 원리가 너무 신기했다. 여러번 되뇌이면서 더 공부해봐야할 것 같다.

5. 무리하게 객체지향 코딩을 하기 보다는 간결하게 문제를 푸는 것이 좋을 것 같다.

6. 문자열을 입력받는 부분을 따로 공부해야할 것 같다.