[백준/Swift] 2589번 : 보물섬

안녕하세요.

https://www.acmicpc.net/problem/2589

2589번: 보물섬

---

문제 풀기 전에 간단하게 문제를 해석하면서 시작하겠습니다.

• 보물섬 지도는 육지(L) 과 바다(W)로 구성되어있습니다.
• 보물섬에서의 이동은 육지(L) , 상 하 좌 우로 이웃한 육지로만 이동할 수 있습니다.
• 이때 한 칸 이동시에 1시간이 걸리는데, 가장 긴 시간이 걸리는 육지 두 곳에 보물이 묻혀있습니다.

저는 이 문제를 bfs를 통해 풀었습니다. 

• dfs를 통한 탐색은 최대한 한 길만 파는 방면, //스택
• bfs는 최대한 넓은 방향으로 동시에 탐색을 할 수 있다는 장점이 있어 BFS 를 사용했습니다. //큐

이 문제에서 최단 거리를 요구하는데,

맨 처음 최단 거리의 시작 좌표를 모르기 때문에 살짝 당황했었습니다.

( 맨 처음 아무 좌표나 bfs 탐색을 하고, 더이상 내려갈 노드가 없을 때 그 좌표 두곳을 기억해야 하나..? )

알고리즘 분류를 살짝 봤고 " 브루트 포스 알고리즘 " 을 사용해야 한다는 것을 알았습니다.

• 브루트 포스 : 가능한 모든 경우의 수 탐색.

아하,, 그렇군

원래 지금까지 제가 풀었던 최단 경로문제는 그냥 특정한 길이 주어진다면 그 길이 총 몇개인지를 파악하는 문제를 풀었다면,

이번에는 특정한 좌표를 시작으로 bfs탐색의 해를 전부 찾는 방식을 써야 해를 구할 수 있는 문제입니다. (신기..)

for y in 0..<HW[0]{ //높이 = HW[0]
    for x in 0..<HW[1]{ //가로 = HW[1]
        if map[y][x] == "L"{ // 특정 좌표 (x,y)가 지도에서 길로 표시되는지?
            let day = bfs(x,y) //탐색!!
            if max < day { max = day } //최단경로인지?
        }
    }
}

 

 

보물섬 지도의 모든 L길을 시작점으로 하는 bfs 탐색 후 최단 경로인지를 비교하면 되는 문제입니다.

 

	import Foundation
//HW[0] == 세로 , HW[1] == 가로
var HW = readLine()!.split(separator: " ").map{Int(String($0))!}
//탐색방향
var direction = [(-1,0),(1,0),(0,-1),(0,1)]
var map = Array(repeating: [String](), count: HW[0])

for i in 0..<HW[0]{
    map[i] = readLine()!.map{String($0)}
}
//최단경로
var max = 0

for y in 0..<HW[0]{ //세로
    for x in 0..<HW[1]{ //가로
        if map[y][x] == "L"{ //특정 좌표 (x,y)가 길인가?
            let day = bfs(x,y) //bfs탐색
            if max < day { max = day } //최단 경로인가?
        }
    }
}
func bfs(_ x :Int , _ y : Int ) -> Int{
    //bfs탐색 결과 저장
    var shortPath = Array(repeating: Array(repeating: -1, count: HW[1]), count: HW[0])
    //최단 경로 길이
    var maxPath = 0
    var queue = [(Int,Int)]()
    queue.append((x,y))
    //시작지점 값 0
    shortPath[y][x] = 0
    while(!queue.isEmpty){
        let (dx,dy) = queue.removeFirst()
        for i in direction{
            let nx = dx + i.0
            let ny = dy + i.1
            if ny < 0 || ny > HW[0] - 1 || nx < 0 || nx > HW[1] - 1{
                continue
            }
            if map[ny][nx] == "L" && shortPath[ny][nx] == -1 {
                //특정 지역 이동 시 1시간
                shortPath[ny][nx] = shortPath[dy][dx] + 1
                if maxPath < shortPath[ny][nx] { maxPath = shortPath[ny][nx]}
                queue.append((nx,ny))
            }
        }
    }
    return maxPath
}
print(max)

 

Come to my Github

 

읽어주셔서 감사합니다!!

 

조언! 지적 정말 감사합니다.. 더 좋고 효율성있는 코드를 배우고 싶습니다.