[Swift][BFS] 백준 1261번 (알고스팟)

요구능력 : BFS에 대한 이해

 

코드설명 : 

 

이 문제를 푸는 방법은 여러가지가 있겠지만, 저는 BFS에서 가중치를 이용해서 문제를 풀었습니다.

 

아래는 이 문제에서의 핵심코드입니다.(제가 생각하기에..)

arr배열은 입력받은 배열로 1이면 벽, 0이면 뚫려있는공간을 의미합니다.

dist배열은 미리 모두 Int.max값으로 초기화 해놨는데, 그 이유는 비교해서 가중치 값을 작은값으로 치환하기 위해서입니다.

아래에서 어떤느낌으로 가중치가 가중되는지 그림으로 그려봤습니다.

if arr[nx][ny] == 1{
        if dist[nx][ny] > dist[pop.0][pop.1] + 1{
            dist[nx][ny] = dist[pop.0][pop.1] + 1
            queue.append((nx, ny))
        }


    }else if arr[nx][ny] == 0 {
        if dist[nx][ny] > dist[pop.0][pop.1]{
            dist[nx][ny] = dist[pop.0][pop.1]
            queue.append((nx,ny))
        }
    }

 

 

후기 : 이런문제도있구나 싶은문제 하나추가..

이런 최소경로 구할때는 가중치를 활용해줘야 하는구나..

억지로 이해중이다..

let mn = readLine()!.split(separator: " ").map{Int(String($0))!}
let m = mn[0]
let n = mn[1]
var arr:[[Int]] = [[]]
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
var dist = Array(repeating: Array(repeating: Int.max, count: 101), count: 101)
var queue: [(Int, Int)] = []
for _ in 1...n{
    arr.append(readLine()!.map{Int(String($0))!})
}
arr.removeFirst()

func bfs(){
    queue.append((0, 0))
    dist[0][0] = 0
    while !queue.isEmpty{
        let pop = queue.removeFirst()

        for i in 0...3{
            let nx = pop.0 + dx[i]
            let ny = pop.1 + dy[i]
            if nx >= 0 && nx < n && ny >= 0 && ny < m{
                if arr[nx][ny] == 1{
                    if dist[nx][ny] > dist[pop.0][pop.1] + 1{
                        dist[nx][ny] = dist[pop.0][pop.1] + 1
                        queue.append((nx, ny))
                    }
                    
                    
                }else if arr[nx][ny] == 0 {
                    if dist[nx][ny] > dist[pop.0][pop.1]{
                        dist[nx][ny] = dist[pop.0][pop.1]
                        queue.append((nx,ny))
                    }
                }
            }
        }
    }
}
bfs()
print(dist[n - 1][m - 1])