본문 바로가기

백준 PS일지/DFS&BFS

[백준/Swift] 17086 : 아기 상어2

 

 

 


17086 : 아기 상어2 / 문제 소개

 

N×M 크기의 공간에 " 1 "  로 표현된 아기 상어 여럿이 존재한다.

아기 상어한테 닿지 않는 최대 안전 거리를 구하는게 이 문제이다.


풀이 과정

 

  1. 완전 탐색으로 맵의 모든 0인 곳에서 아기 상어가 존재 " 1 " 인 지점까지 안전거리 탐색을 한다
  2. BFS로 구현하면 쉽게 파악할 수 있다.
  3. 주의할 점은 아기 상어를 탐색할 때 상하좌우 + 대각선까지 탐색해야 한다.

이 문제를 풀 때 방문체크를 Int로 +1 씩 늘려서 할수 있지만 나는 튜플로 했다.

queue에 x,y,이전에 방문했던 시간을 저장함으로 안전거리를 탐색해 나갔다!!\


코드 구현

 

import Foundation
// 좌 우 상 하 대각선 탐색
let direction = [(-1,0),(1,0),(0,1),(0,-1),(-1,-1),(-1,1),(1,-1),(1,1)]
/**
 * height = N
 * width  = M
 * map   = 상어 1 과 상어가 없는 0이 들어있는 맵 정보
 */
class mapInfo
{
    let height : Int
    let width  : Int
    var map    : [[Int]]
    init()
    {
        let nm     = readLine()!.split(separator: " ").map{Int(String($0))!}
        height = nm[0]
        width  = nm[1]
        map    = Array(repeating: [Int](), count: height)
        for i in 0..<height
        {
            map[i] = readLine()!.split(separator: " ").map{Int(String($0))!}
        }
    }
}
/**
 * 메모리 초과 걸리지 않도록 이전에 탐색한 곳은 visited 체크를 통해 더이상 큐에 넣지 않았다.
 */
func BFS(_ x : Int,_ y : Int, _ m : mapInfo, _ res : inout Int)
{
    var visited   = Array(repeating: Array(repeating: false, count: m.width), count: m.height)
    var queue     = [(x,y,0)]
    var index     = 0
    visited[y][x] = true
    while queue.count != index
    {
        let (curX,curY,prevTime) = queue[index]
        index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx, curY+dy)
            if nx < 0 || nx > m.width - 1 || ny < 0 || ny > m.height - 1
            {
                continue
            }
            if m.map[ny][nx] == 1
            {
                res = max(res,prevTime + 1)
                return
            }
            if !visited[ny][nx] && m.map[ny][nx] == 0
            {
                queue.append((nx,ny,prevTime + 1))
                visited[ny][nx] = true
            }
        }
    }
    
}

func BOJ_17086()
{
    var result = 0
    let mapInfo = mapInfo()
    //완전 탐색
    for y in 0..<mapInfo.height
    {
        for x in 0..<mapInfo.width
        {
            if mapInfo.map[y][x] == 0
            {
                BFS(x, y, mapInfo, &result)
            }
        }
    }
    print(result)
}
BOJ_17086()

 

visit my github