[백준/Swift] 2665 : 미로 만들기 문제 풀이와 반례

 

 

• BOJ_2665.swift

• 2665 : 미로 만들기/ 문제 소개
• 풀이 과정
• 코드 구현

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

2665번: 미로만들기

2665 : 미로 만들기 / 문제 소개

 

미로는 n x n 크기이다.

시작(0,0)에서 끝(n-1,n-1)으로 가는것이 목적인데 검은 방은 흰 방으로 바꾸고 지나가야 한다. 되도록이면 적은 수의 검은 방 색을 흰 방으로 만들며 끝 지점에 도착하고 싶다.

만일 흰 방으만 가는 길이 존재할 경우 굳이 검은방을 흰 방으로 바꾸면서 그 방을 지나가지 않아도 되므로 답은 0이다.

풀이 과정

 

bfs 탐색으로 이 문제를 풀었다.

검 -> 흰 방으로 Fix(수정한) 방을 기록하기 위해 2차원 배열을 만들었다.

 

초기 배열의 값들은 9999로 구성되어있다.

추후 방을 지날 때 더 검 -> 흰으로 바꾸며 지나가는데, queue에 있던 탐색해야할 좌표가 방문할 좌표의 (검->흰)바꾼 개수보다 더 적은 방이 있으면 그 방을 최소로 바꾸며 방문한 값으로 새로 갱신해 가면서 문제를 풀어나갔다.

---

  반례

input

4
1000
0001
0001
0001

ans : 3

 

input

5
11111
00001
11111
10000
11111

ans : 0

 

input

5
11111
00000
11111
00000
11111

ans : 2

 

input

5
11111
00000
00000
00000
00001

ans : 3

 

코드 구현

 

import Foundation
typealias Element = (x: Int, y : Int)
let direction     = [(-1,0),(1,0),(0,1),(0,-1)]
/*
    - Param queue : 방 탐색할 좌표
    - Param index : 큐 훑을 index
    - Param fixed : 맵을 탐색할 때 이전에 (검->흰)으로 바꾼 개수가 적은 값으로 값을 갱신해 나갔다.
    
 */
func BFS(_ n : Int, _ map : inout [[Int]])
{
    var queue = [Element]()
    var index = 0
    var fixed = Array(repeating:Array(repeating:9999, count:n),count:n)
    fixed[0][0] = 0
    queue.append((0,0))
    while queue.count != index
    {
        let (curX,curY) = queue[index]
        index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx<0 || nx>n-1 || ny<0 || ny>n-1
            {
                continue
            }
           
            if map[ny][nx] == 1 && fixed[ny][nx] > fixed[curY][curX]
            {
                fixed[ny][nx] = fixed[curY][curX]
                queue.append((nx,ny))
            }
            else if map[ny][nx] == 0 && fixed[ny][nx] > fixed[curY][curX]
            {
                fixed[ny][nx] = fixed[curY][curX] + 1
                queue.append((nx,ny))
            }
        }
    }
    print(fixed[n-1][n-1])
}

/*
    - Param n   : 맵 크기
    - Param map : (흰,검은 방)맵 정보
 */
func BOJ_2665()
{
    let n   = Int(readLine()!)!
    var map = Array(repeating: [Int](),count : n)
    for i in 0..<n
    {
        map[i] = readLine()!.map{Int(String($0))!}
    }
    BFS(n, &map)
}
BOJ_2665()

 

visit my github