글 읽기 - 길찾기 알고리즘 대각선 탐색

qkreltms 5년 전 0

안녕하세요.

1 1 1

위와 같은 3*3 공간이 있을 때

대각선을 이용하지 않으면 오른쪽 아래 끝까지 도착할 때 4번이 걸리고

대각선을 이용하면 2번이 걸립니다.

제 소스코드를 보면(오른쪽 아래 대각선만 구현), 대각선 탐색을 추가했을 때 눈에 뛸정도로 시간이 많이 소요됩니다.

떠오른 해결방법은 동적계획법이나, 다익스트라 같은 다른 알고리즘 사용인데,

대각선 이동시 어떻게 하면 더 빠르게 할 수 있을까요?

class DFS_MapSearching:
    def __init__(self):
        self.row, self.col = list(map(int, input("행, 열:").split()))
        self._map = [[0] * self.row for _ in range(self.col)]
        self._min = self.row * self.col

        print("탐색할 지도:")
        for i in range(self.col):
            for j in range(self.row):
                self._map[i][j] = 1
                print(self._map[i][j], end=" ")
            print("")

        # 생성된 배열공간은 row 까지인데 탐색은 row + 1 까지하므로, 오버플로우 방지할 수 있도록 -1씩 해줌
        self.row -= 1
        self.col -= 1

        self.dfs(0, 0, 0)
        print("최단 거리 : %d" % self._min)

    def dfs(self, x, y, length):
        if x is self.row and y is self.col:
            if self._min > length:
                self._min = length
                return

        self._map[y][x] = 0

        # 오른쪽 아래 대각선 이동
        if y < self.col and x < self.row and self._map[y + 1][x + 1] is 1:
            self.dfs(x + 1, y + 1, length + 1)

        # 왼쪽 이동
        if x > 0 and self._map[y][x - 1] is 1:
            self.dfs(x-1, y, length+1)
        # 오른쪽 이동
        if x < self.row and self._map[y][x + 1] is 1:
            self.dfs(x+1, y, length+1)
        # 아래로 이동
        if y < self.col and self._map[y + 1][x] is 1:
            self.dfs(x, y+1, length+1)
        # 위로 이동
        if y > 0 and self._map[y - 1][x] is 1:
            self.dfs(x, y-1, length+1)

        self._map[y][x] = 1


DFS_MapSearching()

##
행, 열: 5 5
탐색할 지도:
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
최단 거리 : 4
##

jh05013 5년 전 0

최단거리는 무조건 DFS 말고 BFS입니다. DFS로는 최단거리를 효율적으로 찾을 수 없습니다.

qkreltms 5년 전 0

흠.. 몰랐는데 찾아보니까 BFS가 더 빠른것 같네요 덕분에 알아갑니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

길찾기 알고리즘 대각선 탐색

qkreltms 5년 전 0

jh05013 5년 전 0

qkreltms 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말