99클럽 코테 스터디 4기 9일차 TIL - 백준: 나이트의 이동(7562) Swift & Python

레일리·2024년 11월 5일
0
post-thumbnail

ℹ️ 문제 정보

플랫폼번호제목유형난이도언어
백준7562나이트의 이동BFS실버1Swift, Python

🚀 나의 접근 방법

이 문제는 나이트가 최소 몇 번 만에 이동할 수 있는지(최단거리)를 구하는 것이기 때문에 BFS를 이용하면 된다.

물론 DFS로도 해결할 수 있지만 탐색할 때 마다 항상 비교하며 최소 거리를 갱신해 줘야 해서 비효율 적이다. (보통 최단거리는 BFS를 사용한다)

BFS를 사용하기로 결정했으면 나이트가 이동할 방향을 정의해야 한다.

나이트는 위와 같이 움직일 수 있다. 그러면 8가지의 이동을 아래와 같이 정의할 수 있다.

let dx = [-2, -1, 1, 2,  2,  1, -1, -2]
let dy = [ 1,  2, 2, 1, -1, -2, -2, -1]

위 방향 배열을 아래와 같이 for 문으로 접근하여 사용하면 된다.

for i in 0..<8 {
	let nx = x + dx[i]
	let ny = y + dy[i]
}

이를 활용해 BFS를 사용하여 원하는 좌표를 찾으면 이동한 거리를 출력하면 된다.

✍️ 나의 코드

Swift

let T = Int(readLine()!)!

for _ in 0..<T {
    let length = Int(readLine()!)!
    let start = readLine()!.split(separator: " ").map{ Int($0)! }
    let (startX, startY) = (start[0], start[1])
    let end = readLine()!.split(separator: " ").map{ Int($0)! }
    let (endX, endY) = (end[0], end[1])
    
    var graph = Array(repeating: Array(repeating: false, count: length), count: length)
    
    let dx = [-2, -1, 1, 2,  2,  1, -1, -2]
    let dy = [ 1,  2, 2, 1, -1, -2, -2, -1]
    
    func bfs(_ x: Int, _ y: Int) {
        var queue = [(x, y, 0)]
        var idx = 0
        graph[x][y] = true
        
        while queue.count > idx {
            let n = queue[idx]
            let x = n.0
            let y = n.1
            let count = n.2
            
            if x == endX && y == endY {
                print(count)
                break
            }
            
            for i in 0..<8 {
                let nx = x + dx[i]
                let ny = y + dy[i]
                
                if nx < 0 || nx > (length - 1) || ny < 0 || ny > (length - 1) {
                    continue
                }
                
                if !graph[nx][ny] {
                    graph[nx][ny] = true
                    queue.append((nx, ny, count+1))
                }
            }
            idx += 1
        }
    }
    bfs(startX, startY)
}

Python

from collections import deque

T = int(input())

for _ in range(T):
    length = int(input())
    startX, startY = map(int, input().split(" "))
    endX, endY = map(int, input().split(" "))

    graph = [[False] * length for i in range(length)]

    dx = [-2, -1, 1, 2,  2,  1, -1, -2]
    dy = [ 1,  2, 2, 1, -1, -2, -2, -1]

    def bfs(x, y):
        queue = deque([(x, y, 0)])
        graph[x][y] = True

        while len(queue) > 0:
            n = queue.popleft()
            x, y, count = n[0], n[1], n[2]

            if x == endX and y == endY:
                print(count)
                break

            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]

                if nx < 0 or nx > length - 1 or ny < 0 or ny > length - 1:
                    continue
                
                if not graph[nx][ny]:
                    queue.append((nx, ny, count + 1))
                    graph[nx][ny] = True

    bfs(startX, startY)

🤔 회고 및 개선사항

DFS와 BFS 선택

사실 처음에 DFS로 접근했다. 그러자 뭔가 필요 이상으로 복잡해졌다는 것을 느끼고 다시 BFS로 해결했다. 아직 탐색을 위해 DFS와 BFS 중 어느 것을 선택해야 하는지 빠르게 감이 안 잡히는 것 같다.

아래 블로그를 참고하여 추가 적으로 정리했다.
참고 : PS를 하며 느끼는 DFS와 BFS 선택의 기준

DFS
1) 연결된 그래프를 완전 탐색하는데 활용가능
2) 모든 경우를 하나하나 다 탐색을 해야될경우 이용(ex. 조합, 순열 모든 경우의수를 하나한 다 찾고자할때)
3) 위의 개념과 결부된 깊이 우선탐색이라는 개념을 가진 순열, 조합 구현에 활용

BFS
1) DFS와 마찬가지로 연결된 그래프를 완전탐색하는데 활용
2) depth(깊이)를 계산해야되는 문제에 활용(위의 문제예의 경우 최단경로의 길이 == depth(깊이))
3) 위의 개념과 결부된 가중치가 같은 그래프에서 최단거리를 찾는데 활용

profile
나야, 개발자

0개의 댓글