17086 : 아기 상어2 / 문제 소개
N×M 크기의 공간에 " 1 " 로 표현된 아기 상어 여럿이 존재한다.
아기 상어한테 닿지 않는 최대 안전 거리를 구하는게 이 문제이다.
풀이 과정
- 완전 탐색으로 맵의 모든 0인 곳에서 아기 상어가 존재 " 1 " 인 지점까지 안전거리 탐색을 한다
- BFS로 구현하면 쉽게 파악할 수 있다.
- 주의할 점은 아기 상어를 탐색할 때 상하좌우 + 대각선까지 탐색해야 한다.
이 문제를 풀 때 방문체크를 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
'백준 PS일지 > DFS&BFS' 카테고리의 다른 글
[백준/Swift] 3187 : 양치기 꿍 문제 풀이 (0) | 2022.07.14 |
---|---|
[백준/Swift] 16236 : 아기 상어 문제 뿌수기!! (0) | 2022.07.12 |
[백준/Swift] 18405 : 경쟁적 전염 (0) | 2022.07.05 |
[백준/Swift] 6593 : 상범 빌딩 (0) | 2022.07.04 |