https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
16236 : 아기 상어 / 문제 소개
문제를 명확하게 이해해야 햇갈리지 않고 풀 수 있다....
초기 아기상어
- 크기 : 2 (== 잡아먹을 수 있는 물고기는 2보다 낮은 1)
- 1초에 상 하 좌 우로 이동한다.
- 크기가 2 인 물고기는 잡아 먹을 수 없지만 이동은 가능하다.
- 크기가 자신보다 큰 (3이상) 인 물고기는 지나갈 수 없다.
아기상어가 물고기를 먹을 때의 조건 (중요)
- 상 하 좌 우 로 이동 가능.
- 먹을 수 있는 물고기가 1마리면 그 물고기 먹으로 간다.
- 상 하 좌 우에 물고기가 2마리라면? 가장 위에 있는 물고기를 먹는다.
- 여러 마리라면? 가장 왼쪽에 있는 것을 먹는다.
- 자신보다 작은 크기의 물고기만 먹을 수 있고 먹을 때마다 경험치가 증가한다.
- 그경험치가 자신의 크기만해지면 자신은 레벨업되고 경험치는 0으로된다!
개인적으로 이 부분에서 많이 했갈렸다( 틀린 접근 경험 공유 중 ..)
dfs로 풀자니.. 여러마리 일때는 먹어야 하는 순서가 정해져 있기 때문에 bfs를 활용한 문제라고 생각했다.
그렇다면 bfs로 어떻게 풀까?
문제 풀 당시 초반에 내가생각한 bfs는 일단 상어는 1초마다 무조건 움직인다. 상 하 좌 우로
이 그림에서 상어는 1초 뒤에
이런 위치로 이동하겠지? 근데 그렇다면
그다음에 먹을 수 있는 방법은 2가지가 존재한다.
(1,2) 에 상어가 있다면 먹을 수 있는 경우는 단 한가지 (0,2) 먹이를 먹는게 최선이다 ( 좌 그림)
(2,1) 에 상어가 있다면 먹을 수 있는 경우는 단 한가지 (2,0) 먹이를 먹는게 최선이다 ( 우 그림)
bfs를 통해 상어가 이렇게 2개의 위치로 이동했을 때 각각의 상태에서 인접한 물고기는 단 한마리한다.
Greedy하게..아니 그냥 먹을 수 있는 물고기는 딱 한개니까 문제의 조건에 부합되는 게 없다. 인접한 물고기 먹는게 최선의 방법이다.
근데 이렇게 먹을 수 있는 경우의 수는 2개 존재한다(좌,우 그림). 둘중 한개를 선택해야한다. 어차피 문제에서 주어진 조건에 다 만족하니까 그냥 아무거나 먼저 탐색 queue에 온 좌표로 선정해서 먹고 계속해서 탐색을 하면 되려나?
그렇게 그냥 그 한마리를 먹으며 탐색해나갔다. 근데 이렇게 문제를 접근 할 경우
이 문제에서 제시된 답보다 큰 경우의 답이 나온다. 즉 내가 풀었던 방법이 오답이라는 것이다.
원하는게 뭘까?
bfs는 써야하는데 ,, 뭐지?? 상어가 bfs의 주인공이 아닌가? 물고기가 주인공인가?!!
아까 위에서 언급한 두가지 상황에서 무작위로 선정한게 틀렸다는건데.. 상어는 1초마다 이동해야하고,
이동 할 경우에 두가지의 먹이를 먹는 경우가 나온다.
근데 문제를 계속해서 읽다 보니까 아기상어는 1초에 상하 좌 우로 이동할 수 있는데!!!!!! (필수로 이동하는게 아님)
먹을 수 있는!! 물고기가 1마리면!!!! 그때 이동한답니다.
무조건 1초에 상 하 좌 우로 이동하는게 아니라.. 상어가 최소로 이동한 최소 거리에 먹이가 존재할 때 비로소 상어는 그 먹이를 먹으로 가는 것입니다...
그러면 먹이가 있는지 bfs로 탐색만하고 탐색 후에 먹이가 발견되면 문제의 조건에 따라서 상어가 먹으로 가는구나!!
아하.. 이제서야 문제를 이해했다.. (저만 이런가요? ㅠㅠㅠㅠㅠ 더 연습해야겠네요)
아까 그린 그림은 틀린 그림입니다.
파란색위치에 가면 상어는 먹이를 먹을 수 있나? 오호 (0,2) 와 (2,0) 에 먹이가 있네 둘다 상어가 이동할 최소 거리는 2로 같네
이때 문제에서 조건을 보면 1마리보다 많다면 위쪽에 있는 먹이를 먹을 수 있겠네. (아까와는 다르게 명확한 선택지를 결정 할수 있었다.)
그렇다면 그림 3과 같은 경우에는 뭐를 우선으로 접근해 가야할까?
(만일 이 글을 읽는다면 잠시 생각해보세요)
일단 상어는 파란색으로 이동x 먹이 없기 때문 그렇다면 (최소거리 2) 주황색으로 최소거리 2일때는 먹이가 있나? 어 그런데 그 옆에 인접한 곳(초록 좌표)에 먹이가 있네!! 그럼 최소거리 3으로 이동하면 먹이를 먹을 수 있네.
이때 먹이는 3가지 경우인데 문제의 조건을 적용시킨다면?
문제의 조건을 여러번 따졌는데 저는 여기서 이런 결론을 내렸습니다.
- 먹을 수 있는 물고기가 1마리면 그 물고기 먹으로 간다.
- 물고기 2마리라면? 가장 위에 있는 물고기를 먹는다.
- 여러 마리라면?(3마리 이상) 가장 위에 있으면서, 가장 왼쪽에 있는 것을 먹는다.
따라서 (1,0)을 먹고 또다시 먹이를 찾아 탐색해 나갈 것입니다..(를 반복)
풀이 과정
상어의 현재 위치
typealias sharkType = (x : Int, y : Int, size : Int, exp : Int)
var shark : sharkType = (0,0,2,0)는 저장시키고, exp라고하는것은 상어가 먹이를 먹은 경험치입니다. 같을 때 상어는 성장!! +1 랩업
초기 입력받은 상어와 물고기 위치가들어있는 map : [[Int]] 에서 상어의 위치를 0으로 만듭니다.
(상어는 다시 먹이를 찾아 다른곳으로 갓다가 초기 입력받은 위치로 올 수 도 있기 때문입니다.
그리고 상어의 위치를 통해 bfs탐색을 하며 먹이를 찾아나섭니다.
이때 위에서 그린 그림4의 우측과 같은 경우에 먹이를 먹을 수 있는 좌표가 특정 최소 거리일때 3개 이상 존재할 수 있는데
이렇게 물고기가 나올 경우까지 현재 상어의 위치에서 bfs탐색을 해나갑니다.
특정 최소 거리에 존재하는 먹이 좌표를 eatList에 저장시킨 후
typealias Element = (x : Int, y : Int, time : Int) //타임은 상어가 이동할 최소 거리를 나타냅니다
var eatList = [Element]()eatList를 위 문제의 조건에 따라서 , (위에)그림 4일때 제가 먹이를 먹을 수 있었던 문제 조건에 대한 결론을 적용시키면서 eatList를 소팅했습니다. 거기서 맨 앞에 sort된 좌표가 문제 조건을 만족하는 물고기이므로
shark의 좌표는 그 물고기가 있던 좌표(물고기 먹음)로 바뀌고 0으로 바꾸면서 다시 bfs탐색을 이어나갑니다!!
코드 구현
import Foundation
//탐색 방향
let directon = [(-1,0),(1,0),(0,-1),(0,1)]
/*
- param Element : ( x 탐색 좌표, y 탐색 좌표, time 최소 거리)
- param sharkType : ( x 샤크 있는곳, y 샤크 있는곳, size 현재 샤크 크기, exp 특정 크기 일 때 샤크가 먹이 먹은개수)
*/
typealias Element = (x : Int, y : Int, time : Int)
typealias sharkType = (x : Int, y : Int, size : Int, exp : Int)
/*
TODO : 상어가 위치한 곳에서부터 시작해서 bfs탐색을 하며 먹을 수 있는 물고기를 찾아 나선다.
문제에서 언급된 조건에 의해 최소거리 이면서도 최소 거리에서 물고기가 2개, or 3개 이상일 때 가장 최적의 물고기를 먹을 수
있도록 먹이를 sorting한다.
- param visited : 중복된 방문 피하기 위해 방문 체크
- param queue : 상어가 이동 할 수 있는 좌표들 저장
- param eatList : 상어가 특정 최소 거리일 때 먹을 수 있는 물고기들 전부 저장
- param index : queue배열을 탐색하기 위한 인덱스
추후 eatList에서 소팅이 가장 중요함. 이 문제의 핵심?!
*/
func BFS(_ n : Int,_ isRunning : inout Bool,_ time : inout Int, _ shark : inout sharkType, _ map : inout [[Int]])
{
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var queue = [Element]()
var eatList = [Element]()
var index = 0
//상어 현 x,y위치 그리고 이동 거리 0
queue.append((shark.x,shark.y, 0))
visited[shark.y][shark.x] = true
while queue.count != index
{
let (curX,curY,curTime) = queue[index]
index += 1
for (dx,dy) in directon
{
let (nx,ny) = (curX+dx, curY+dy)
if nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1
{
continue
}
if map[ny][nx] <= shark.size && !visited[ny][nx]
{
if map[ny][nx] == 0 || map[ny][nx] == shark.size
{
visited[ny][nx] = true
queue.append((nx,ny,curTime + 1))
}
else if map[ny][nx] < shark.size
{
eatList.append((nx,ny,curTime + 1))
visited[ny][nx] = true
}
}
}
}
/*
* 만약 eatList(먹이를 먹을 수 있는 좌표)가 비어있지않다면 샤크는 계속해서 먹이를 먹을 수 있으므로
isRunning = true!!
* 같은 시간(== 같은 최소 거리 일 때)
* 리스트에 원소.y가 그림 4의 경우라면? 둘다 위에인데 ? 그럼 맨 왼쪽꺼!!
* 그게 아니면 맨 위에 좌표
* 그게 아니라면 최소거리(time)가 낮은 것 부터
*/
if !eatList.isEmpty
{
eatList.sort
{
if $0.time == $1.time
{
if $0.y == $1.y
{
return $0.x < $1.x
}
else
{
return $0.y < $1.y
}
}
else
{
return $0.time < $1.time
}
}
// 최적의 먹잇감을 샤크가 먹고 그 좌표로 샤크의 위치를 대체합니다. 이때 래밸업 할 것인가 겸치만 증가할 것인가?
let eat = eatList.first!
if shark.size > map[eat.y][eat.x]
{
time += eat.time
isRunning = true
if shark.size == shark.exp + 1
{
shark = ((eat.x,eat.y,shark.size + 1, 0))
}
else
{
shark = ((eat.x,eat.y,shark.size, shark.exp + 1))
}
map[shark.y][shark.x] = 0
}
}
}
/*
- param n : 맵 크기
- param map : 맵 정보
- param shark. : 샤크의 저장 위치 ( 추후 map에서 샤크의 초기 위치 9 -> 0 으로 바꾼다.)
- param time : 샤크의 이동 거리
- param isRunning : 샤크가 먹이를 먹을 수 있는가?
샤크가 먹이를 먹을 수 있으면 true 더이상 eatList에 원소가 없다면 탐색 종료
*/
func BOJ_16236()
{
let n = Int(readLine()!)!
var map = Array(repeating: [Int](), count: n)
var shark : sharkType = (0,0,2,0)
var time = 0
var isRunning = true
for y in 0..<n
{
map[y] = readLine()!.split(separator:" ").map{Int(String($0))!}
if map[y].contains(9)
{
let x = map[y].firstIndex(of: 9)
shark = (x!,y,2,0)
map[y][x!] = 0
}
}
while isRunning
{
isRunning = false
BFS(n, &isRunning, &time, &shark, &map)
}
print(time)
}
BOJ_16236()
visit my github
'백준 PS일지 > DFS&BFS' 카테고리의 다른 글
| [백준/Swift] 2665 : 미로 만들기 문제 풀이와 반례 (0) | 2022.07.15 |
|---|---|
| [백준/Swift] 3187 : 양치기 꿍 문제 풀이 (0) | 2022.07.14 |
| [백준/Swift] 17086 : 아기 상어2 (0) | 2022.07.10 |
| [백준/Swift] 18405 : 경쟁적 전염 (0) | 2022.07.05 |
