✅ BFS ✅ 최단경로

문제

링크

풀이

1. 문제 접근

• 테스트 케이스 반복
• 시작점과 목표지점이 정해져 있다
• 나이트가 이동할 수 있는 위치는 한 지점에서 총 8가지로,
  • dx = {1,2,-1,-2,-1,-2,1,2}
  • dy = {2,1,2,1,-2,-1,-2,-1}

2. 문제 해결 로직 (풀이법)

최단거리 문제이므로 BFS 사용

• 보통의 최단거리 문제와 다른 점은 나이트가 이동할 수 있는 경우가 상하좌우가 아니라는 점 (풀이는 동일)
• 나이트가 이동하여 목표지점까지 도달하지 못하는 경우에 대한 언급은 없으므로 신경쓰지 않아도 될듯
• 이전에 갔던 칸에 다시 갈 경우에 굉장히 비효율적이므로 (시간초과 나올듯) 이미 한번 방문한 칸은 체크해가며 이동해야 한다.
  • 처음 체스판이 시작 위치를 제외하고 모두 말이 없는 상태이므로 visited[][]를 따로 만들 필요 없이 map[][]의 방문한 칸에 체크해주면 다음번에 방문 해도 되는지 안되는지 판별 가능

의사코드

bool map[301][301]
int dist[301][301]
queue<pair<int, int>> que

dx[8] = {1,2,-1,-2,-1,-2,1,2}
dy[8] = {2,1,2,1,-2,-1,-2,-1}

BFS(){
	while(!que.empty){
    	x = que.front.second
        y = que.front.first
        que.pop
        
        for(i : 0 ~ 7){
        	nx = x + dx[i]
            ny = y + dy[i]
            
            if(nx < 0 || ny < 0 || nx >= l || ny >= l) continue
            if(map[ny][nx] == true) continue // 이미 지나왔던 위치일 경우
            
            que.push({ny, nx})
            map[ny][nx] = true
            dist[ny][nx] = dist[y][x] + 1
            
            if(ny == tx && nx == ty){ // 좌표를 뒤집어서 생각했기 때문에 ny와 tx 비교, nx와 ty 비교 (1743 음식물 피하기 포스팅 설명 참고)
            	cout << dist[ny][nx]
                return
            }
        }
        
    }
}

main(){
	cin >> T // 테스트케이스
    while(T--){
    	cin >> l // 체스판 한 변의 길이
        cin >> sx >> sy // 시작(start) 위치 
        cin >> tx >> ty // 목표(target) 위치
        
        que.push({sx, sy})
        map[sx][sy] = true // 다시 돌아올 경우 방지하기 위해, 시작위치 map에 표시
        
        BFS()
        
        while(!que.empty) que.pop // que 초기화
    }
    
}

3. 시간 복잡도 분석

O(N^2)

4. 문제에서 중요한 부분

이동 가능한 경로가 상하좌우가 아니었던 점 (풀이는 동일)
시작점과 목표지점이 정해져 있는 문제라는 점 정도.?
특별한건 없었음
유의할 점은 BFS에서 입력받은 좌표를 뒤집어서 생각했기 때문에 ny와 tx 비교, nx와 ty 비교 해야 한다는 점
( 1743 음식물 피하기 설명 참고 )