[백준/Swift] 1697 : 숨바꼭질

 

• Todo List

• 문제 소개
• 풀이 과정
• 코드 구현
• 개선해야 할 것

 

 

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

1697번: 숨바꼭질

 

문제 소개

 

한 수평선의 어딘가에 수빈이랑 동생이 있습니다. 

수빈이는 걷거나, 순간이동을 해서 동생을 찾아야 하는데 이때 가장 빠른시간을 구하는 문제입니다.

(맨 처음에 서로 다른 x,y축인줄..)

 

이 문제도 BFS로 풀 수 있습니다. 제가 기존에 풀었던 문제 대부분은 탐색을 하기 위해 "상, 하, 좌, 우"가 문제에서 주어졌다면.. 이문제는 bfs 탐색을 하기 위해서  특정 위치 -1 , 특정 위치 +1, 특정 위치 * 2 를 통해서 수빈이가 있는 좌표까지 탐색하 가면 됩니다!!

 

   문제에서 주어진 키워드

• 수빈이의 점 = N (0과 100,000 사이)
• 동생 점        = K (0과 100,000 사이)
• 수빈이 걸을 때 = (특정 위치)+ 1 , (특정 위치)-1
• 수빈이 순간이동 = (특정 위치)*2
• 걷거나 순간이동은 1초마다 할 수 있다!

 

풀이 과정

 

bfs탐색을 하기 위해서 문제에서 주어진 1초 후에~ 라는 문장을 바탕으로 1초마다 bfs 탐색을 수행했습니다.

이 문제 풀기 전에 탈출 문제 풀었는데 상당히 비슷하네요

 

bfs 탐색을 하기 전에

var queue   = [(Int,Int)]()

튜플 형식의 list를 큐로 선언했습니다.

왼쪽 값은 수빈이가 걷거나, 순간이동해서 도착한 좌표입니다.

오른쪽 값은 방문 당시의 시간입니다.

 

수빈이가 bfs탐색을 하면서 방문한 시간이 현재 시간과 같으면 현재 시간을 +1로 증가하면서 탐색을 이어나갑니다.

 

제가 푼 코드에 의하면. 초기

 

현재 시간(time)은 0 입니다.

초기에 수빈이가 5 좌표였으므로 초기값을 저장할 때는

queue.append((5,0))이 됩니다.

 

이때 현재시간과 queue에 들어있는 시간이 같아질 경우에 현재시간을 +1 합니다.

 

 

그리고 bfs탐색을 수행 후 새로 방문한 좌표들과 그때 시간은 (1초 뒤에 걸을 수 있다! == 1초 뒤에 새로운 좌표로 이동할 수 있다)

이전에 튜플의 오른쪽에 저장된 0 (초) 에서 +1 을 증가시켜 1을 저장합니다.

 

이후 while문을 수행하면서 queue에 들어있는 좌표를 전부 탐색할 때까지 bfs 탐색을 수행합니다.

 

특정 위치에서 탐색을 할 때 저는 클래스를 통해 구현을 했습니다.

 

/**
 * 이 클래스를 통해서 특정 location에 대한 텔레포트, 한칸 앞, 한칸 뒤 연산이 실행됩니다.
 * @param location : 현재 위치
 * @param teleport : 현재 위치 *=2
 * @param front      : 현재 위치 += 1
 * @param back      : 현재 위치 -= 1
 */
class move
{
    var location : Int
    var teleport : Int
    var front    : Int
    var back     : Int
    init(_ location : Int)
    {
        self.location = location
        teleport      = location * 2
        front         = location + 1
        back          = location - 1
    }
}

 

코드 구현

 

 

import Foundation

/**
 * 이 클래스를 통해서 특정 location에 대한 텔레포트, 한칸 앞, 한칸 뒤 연산이 실행됩니다.
 * @param location : 현재 위치
 * @param teleport : 현재 위치 *=2
 * @param front      : 현재 위치 += 1
 * @param back      : 현재 위치 -= 1
 */
class move
{
    var location : Int
    var teleport : Int
    var front    : Int
    var back     : Int
    init(_ location : Int)
    {
        self.location = location
        teleport      = location * 2
        front         = location + 1
        back          = location - 1
    }
}
/**
 * 최초 수빈과 동생의 위치를 입력받는 함수입니다.
 */
class locationDTO
{
    var subin  : Int
    var sister : Int
    init()
    {
        if let input = readLine()
        {
            let subin_sister = input.split(separator: " ").map{Int($0)!}
            subin  = subin_sister[0]
            sister = subin_sister[1]
        }else
        {
            subin  = -1
            sister = -1
        }
    }
}
/**
 * 동생을 찾기위한 탐색(bfs)!! 이 일어나는 함수입니다.
 * @param queue   :  (특정 위치, 시간)
 * @param index    : 큐를 탐색하기 위한 index
 * @param visited   : 특정 위치 방문 기록
 * @param prevSec : 이전 시간 체크!
 *
 * queue에 저장된 시간에 따라서 현재시간이 아니라면 계속적으로 큐에서 원소를 찾아 수빈이가 이동합니다.
 * -> bfs를 구현하기 위해 시간 개념 도입!!
 */
func findSister(_ location : locationDTO, _ second : inout Int)
{
    
    var queue   = [(Int,Int)]()
    var index   = 0
    var visited = Array(repeating: false, count: 100001)
    var prevSec = 0
    visited[0]  = true
    queue.append((location.subin,second))
    visited[location.subin] = true
    
    while queue.count != index
    {
        let locate = queue[index].0
        let nSec   = queue[index].1
        index += 1
        var moved  = move(locate)
        if nSec == second { second += 1 }
        if moved.teleport == location.sister ||
            moved.back == location.sister ||
            moved.front == location.sister
        {
            return
        }
        if moved.teleport > 0 && moved.teleport < 100001
        {
            if !visited[moved.teleport]
            {
                queue.append((moved.teleport,nSec + 1))
                visited[moved.teleport] = true
            }
        }
        if moved.front > 0 && moved.front < 100001
        {
            if !visited[moved.front]
            {
                queue.append((moved.front, nSec + 1))
                visited[moved.front] = true
            }
        }
        if moved.back > 0 && moved.back < 100001
        {
            if !visited[moved.back]
            {
                queue.append((moved.back,nSec + 1))
                visited[moved.back] = true
            }
        }
    }
}
func BOJ_1609()
{
    let location = locationDTO()
    var second   = 0
    if location.sister == location.subin
    {
        print(0)
        return
    }
    findSister(location, &second)
    print(second)
}
BOJ_1609()

 

 

개선해야 할 점

 

 * 그리고 moved의 멤버변수들은 범위가 1~ 100,000 범위여야 합니다.
 * ㅠㅠ;; 범위 나오는거 항상 반례 생각안하고 무조건 제출했다가 항상틀리네요.
 * 꼼꼼해져야겠어요+_+

 

• 첫 제출 때 틀린 이유 : visit를 통해 1~100,000까지 방문체크를 하는데 마이너스가 나온다면? 을 틀리고서야 생각했다..
• 두번째 제출 때 틀린 이유 : 이번엔 반대로 큰 숫자가 나오는 예외처리를 하지 않았다
• 음..
• 문제에서 범위가 주어진다면 그에대한 예외처리와 반례들을 구하는 방법을 연습해야 겠다.
• 그리고 좀 더 꼼곰히...