[백준/Swift] 14442 : 벽 부수고 이동하기 2

 

 

• BOJ_14442.swift

• 14442 : 벽 부수고 이동하기 2/ 문제 소개
• 풀이 과정
• 코드 구현

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

14442번: 벽 부수고 이동하기 2

14442 : 벽 부수고 이동하기2 / 문제 소개

 

N x M의 행렬로 표현되는 맵이 있다.

맵에서 0은 이동할 수 있는 칸, 1은 벽을 나타낸다(벽 부수지 않으면 이동불가)

(1,1)에서 (N,M)까지 이동 해야 한다.

이동하는 도중 벽을 부수고 이동할 때 도착 경로가 짧아진다면 벽울 최대 K개 까지 부수고 이동해도 된다.

최단 경로로 1,1 -> N,M으로 이동하여라!! 는 문제입니다.

풀이 과정

 

음 Swift로 푼 분들 중에 가장 오랜 시간이 결렸습니다 (턱걸이로 겨우 맞은 느낌...)

swift가 백준에선 지원이 후하지 않다고 하던데 C++로 하려다 오기가 생겨서 계속 도전하다 보니 통과했네요.

이 문제를 풀면서 맞는 로직 같은데 시간초과가 상당히 많이 났습니다.

 

우선 저의 경우

bfs 탐색을 통해 1,1에서 N,M으로 갔습니다.

bfs함수에서 

var queue = [(0,0,0,1)] //(x : Int, y : Int, curWallBreak : Int, state : Int)
var index = 0

queue에 좌표들을 저장하면서 진행했습니다.

 

또한 3차원의 visited[curBreak][height][width] 를 활용했습니다.

visited[curBreak]의 경우 0 에서 ~ k까지 (벽을 부순 횟수)

그 뒤에 visited[curBreak] [height][width] 는 특정 좌표를 의미합니다.

curBreak는 벽을 부순 횟수를 의미합니다. 0에서 k까지 벽을 부수면서 이동할 수 있습니다.

 

//탐색할 맵이 0일 때
if info.map[ny][nx] == 0 && !visited[curBreak][ny][nx]
{
    if nx == info.width - 1 && ny == info.height - 1
    {
        return state + 1
    }
    visited[curBreak][ny][nx] = true
    queue.append((nx,ny,curBreak,state + 1))
}
//탐색할 맵이 1일 때
else if info.map[ny][nx] == 1 && info.k  > curBreak && !visited[curBreak+1][ny][nx]
{
    visited[curBreak + 1][ny][nx] = true
    queue.append((nx,ny,curBreak + 1, state + 1))
}

벽이 0이면 현재 벽 부순 횟수에서 방문처리를 하며 그냥 이동하고,

벽이 1 일때 방문할 좌표가 방문하지 않았을 경우에 방문처리를 하면서 이동했습니다.

이게 좀 중요합니다. 특정 좌표로만 봤을 때 이 말은 벽이 1이니까 if !visited[curBreak+1][ny][nx] ... 의 좌표는 당연히 방문을 

하지 않았다고 생각될 건데 이게 큐에 여러개의 좌표가 있을 경우 중복해서 queue에 들어갈 수 있기 때문에 위의 조건식을 부여했습니다.

그래서 벽이 0일때와  1일 때 방문 처리 조건이 다릅니다.

 

그리고 벽이 0일 때 맵의 끝인지를 물어봤습니다. nx,ny에서 도착점에 도달했는지 묻는 경우가

아래의 큐에서 한개씩 꺼낸 따끈따끈한 curX,curY일 때 도착점에 묻는 경우인지의 경우보다 빠르기에 이와 같이 구현했습니다.

while queue.count != index
{
    let (curX,curY,curBreak, state) = queue[index]
    index += 1
    //얘보다 nx,ny에서 물을 때가 좀 더 빨라요
    if curX == info.width - 1 && curY == info.height - 1
	{
        return state
    }
    .
    .
    .

음 .. 

고민해가면서 문제를 풀었는데 시간이 800ms인분들도 있더라구요,, 더 열심히 해야겠습니다.

코드 구현

 

import Foundation
//탐색하기 위한 방향
let direction     = [(0,-1),(1,0),(-1,0),(0,1)]

/*
  Info :맵의 정보가 담겨있는 클래스
 
    - Param height : 세로
    - Param width  : 가로
    - Param k      : 벽을 부술 수 있는 횟수
    - Param map    : 0(길)과 1(벽)이 담긴 맵
 */
class mapInfo
{
    let height : Int
    let width  : Int
    let k      : Int
    var map    : [[Int]]
    init()
    {
        let hwk = readLine()!.split(separator: " ").map{Int(String($0))!}
        height  = hwk[0]
        width   = hwk[1]
        k       = hwk[2]
        map     = Array(repeating:[Int](),count:height)
        for y in 0..<height
        {
            map[y] = readLine()!.map{Int(String($0))!}
        }
    }
}

/*
 Info : (0,0)에서 (N,M)까지 최단 경로로 이동 할 때 벽을 부수면서 이동 시 최단 경로가 존재한다면
        최대 k개까지 벽을 부수면서 이동 할 수 있다.
 
    - Param queue   : [(x : Int, y : Int, curWallBreak : Int, state : Int)]
        x,y = 방문 좌표, 그때 벽 부순 누적횟수 curWallBreak, 이 때의 최단 거리 state
    - Param index   : 큐를 훑기 위한 인덱스
    - Param visited : [curWallBreak카운트][y좌표][x좌표]
        3차원 배열로 선언. 벽을 부술 시 curWallBreak + 1 을 하면서 맵 방문 표시를 함(중복 탐색 방지)
 */
func BFS(_ info : mapInfo) -> Int
{
    var queue   = [(0,0,0,1)]
    var index   = 0
    var visited = Array(repeating: Array(repeating: Array(repeating: false, count: info.width), count: info.height), count: info.k + 1)
    visited[0][0][0] = true
    
    /*
      1 1 1
      0
      인 경우 답 = 1
     */
    if 0 == info.width - 1 && 0 == info.height - 1
    {
        return 1
    }
    while queue.count != index
    {
        //탐색할 좌표 등등 받아옴
        let (curX,curY,curBreak, state) = queue[index]
        index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx < 0 || nx > info.width - 1 || ny < 0 || ny > info.height - 1 || visited[curBreak][ny][nx]
            {
                continue
            }
            //만약 길이라면?
            if info.map[ny][nx] == 0 && !visited[curBreak][ny][nx]
            {
                //답인가?!
                if nx == info.width - 1 && ny == info.height - 1
                {
                    return state + 1
                }
                //방문처리!!
                visited[curBreak][ny][nx] = true
                queue.append((nx,ny,curBreak,state + 1))
            }
            // 벽이라면? + visited[curBreak + 1]일때도 중복해서 방문하지 않았다면?
            else if info.map[ny][nx] == 1 && info.k  > curBreak && !visited[curBreak+1][ny][nx]
            {
                visited[curBreak + 1][ny][nx] = true
                queue.append((nx,ny,curBreak + 1, state + 1))
            }
        }
    }
    return -1
}
func BOJ_14442(){
    let m = mapInfo()
    print(BFS(m))
}
BOJ_14442()

 

visit my github