본문 바로가기

백준 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