요구능력 : BFS(이전 방문 좌표와 거리비교)
코드설명 :
이 문제에서 핵심
1. 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
2. 아기상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.
3. 아기상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
4. 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
5. 더 이상 먹을 수 있는 물고기가 없다면 아기상어는 엄마상어에게 도움을 요청한다.(종료조건)
6. 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러 간다
7. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그런 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
8. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
조건이 매우 많고 복잡한 문제이다.
전체적인 논리를 보면 상어위치에서 BFS로 먹을 물고기를 찾고 거리를 재고 물고기를 먹은 위치에서 다시 먹을 물고기를 찾고 거리를 재고를 반복하다가 먹을 물고기가 없으면 종료하는 문제이다.
우선 아기상어의 위치에서 시작해야하므로 아기상어의 위치를 확보해야한다.
나는 입력받을때 동시에 아기상어의 위치를 확보하고 아기상어의 위치에 0을 넣어줬다.
아기상어는 결국 이동하기 때문에 현재 아기상어가 있는 위치도 나중에 탐색할 때 지나갈 수 있어야한다.
이렇게 해둬야 나중에 조건줄때 편하다.
for i in 0..<n{
arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
for j in 0..<n{
if arr[i][j] == 9{
sharkX = i
sharkY = j
arr[i][j] = 0
}
}
}
1번을 보면 기본적인 BFS라고 생각이 든다.
하지만, 비슷한 유형을 풀어보지 않았다면 이 문제는 매우 어려울수도있다.내가그랬기때문
위에서 전체적인 논리를 말했듯이 이 문제는 상어의 위치 -> 물고기를 먹은 위치 -> 물고기를 먹은 위치 -> . . . -> 먹을물고기가 없으면 종료이기 때문에 상어의 위치와 물고기의 위치좌표를 저장해주고 몇번 움직였는지도 저장을 해줘야한다.
그 작업을 편리하게 하기위해서 구조체를 선언한것이다. 변수로 관리해도 상관은없다.
2. 아기상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.
3. 아기상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
4. 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
6. 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러 간다
상어 사이즈보다 물고기 사이즈가 더 크면 아무 작업도 못하므로 continue로 넘겨주고
공간의 상태가 0이 아니고 상어 사이즈보다 작다면 먹을 수 있는 물고기가 있다는 말이다.
이 BFS를 돌면서도 먹을 수 있는 물고기가 많이 있을 수 있다.
물고기를 한마리 한마리 찾을 때 마다 beforeShark와 비교해주는것이다.
참고로 beforeShark에 처음에 Int.max를 넣어놓은 이유는 처음에 먹을 수 있는 물고기를 찾게되면 거리가 어떻든간에 우선적으로 찾은걸 집어넣기 위해서이고 그 이후로는 가장 거리가 짧은 물고기의 좌표와 거리가 들어가게 될 것이다.
5. 더 이상 먹을 수 있는 물고기가 없다면 아기상어는 엄마상어에게 도움을 요청한다.(종료조건)
만약 beforeShark.dist의 값이 Int.max 그대로라면 먹을 수 있는 물고기를 찾지 못했다는 말이되므로 종료조건으로 사용할 수 있다.
전에 찾은 먹을 수 있는 물고기의 거리와 현재 찾을 먹을 수 있는 물고기의 거리가 같은경우
7. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기,
가장 위에 있는 물고기를 먹기위해 현재 찾은 물고기의 x(row)값이 더 작다면 좌표를 교체해준다.
7. 그런 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
전에 찾은 먹을 수 있는 물고기와 현재 찾은 먹을 수 있는 물고기의 x좌표가 같다는말은 같은 row에 있다는 말이고 이렇게 row가 같으면 가장 왼쪽에 있는 물고기를 먹어야하므로 전에 찾은 물고기와 비교해서 현재 찾은 물고기의 y(column)값이 더 작다면 좌표를 교체해준다.\
if arr[nx][ny] > size {continue}
if arr[nx][ny] != 0 && arr[nx][ny] < size {
if beforeShark.dist > dist + 1{
//이전(거리가 가장짧은)샤크보다 현재샤크의 거리가 더 가까우면 더 가까운 물고기를 먹으러가야한다.
beforeShark.x = nx
beforeShark.y = ny
beforeShark.dist = dist + 1
}
if beforeShark.dist == dist + 1{//거리가 같을경우
if beforeShark.x > nx{
beforeShark.x = nx
beforeShark.y = ny
beforeShark.dist = dist + 1
}else if beforeShark.x == nx {
if beforeShark.y > ny {
beforeShark.x = nx
beforeShark.y = ny
beforeShark.dist = dist + 1
}
}
}
}
8. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
이전에 찾은 상어의 거리는 while문이 돌때마다 종료조건을 찾고 비교하기위해서 계속해서 Int.max값을 넣어주기 때문에 물고기를 찾았을 때(beforeShark.dist가 Int.max가 아닌 다른 값이 들어왔을 때) totalDist에 따로 더해준다.
그리고 물고기를 먹은칸은 나중에 또 지나갈 수 있게 0으로 초기화해주고
물고기를 한마리 먹을 때 마다 feed를 1씩 감소시켜서 feed가 0이되면 size를 업그레이드해주고 feed를 size로 초기화해서 문제의 조건대로 사이즈크기만큼 물고기를 먹을 때 마다 사이즈를 증가시켜준다.
if beforeShark.dist == Int.max{
print(totalDist)
break
}else{
totalDist += beforeShark.dist
arr[beforeShark.x][beforeShark.y] = 0
feed -= 1
if feed == 0 {
size += 1
feed = size
}
}
}
조건이 너무많아서 설명하는걸 잘 못하겠습니다 ㅠㅠ 혹시나 이해가 안가시는 부분은 댓글 남겨주시면 답변 드리도록 하겟습니다!
후기 : 몇일걸려서 이해하고 다시풀어본문제..
조건같은경우에는 어느정도 코드를 잘짯는데 이전값을 저장해야한다는게 왜 자꾸 생각이 이상한데로 빠졌던건지..
많이 배워가는 문제
let n = Int(String(readLine()!))!
var arr = [[Int]]()
//이전에 먹은 물고기의 위치와 거리가 반드시 필요한데 저장해놔야됨. 그래서 구조체 사용.
struct Shark{
var x: Int
var y: Int
var dist: Int
}
var sharkX = 0
var sharkY = 0
let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]
for i in 0..<n{
arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
for j in 0..<n{
if arr[i][j] == 9{
sharkX = i
sharkY = j
arr[i][j] = 0
}
}
}
func bfs(_ sharkX: Int, _ sharkY: Int){
var size = 2
var feed = 2
var totalDist = 0
var beforeShark = Shark(x: sharkX, y: sharkY, dist: 0)
while true{
beforeShark.dist = Int.max
var queue = [((Int, Int), Int)]()
var visited = Array(repeating: Array(repeating: false, count: 401), count: 401)
queue.append(((beforeShark.x, beforeShark.y), 0))
var idx = 0
while queue.count > idx {
let pop = queue[idx]
let x = pop.0.0
let y = pop.0.1
let dist = pop.1
idx += 1
for i in 0..<4{
let nx = x + dx[i]
let ny = y + dy[i]
if nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] {continue}
if arr[nx][ny] > size {continue}
if arr[nx][ny] != 0 && arr[nx][ny] < size {
if beforeShark.dist > dist + 1{
//이전(거리가 가장짧은)샤크보다 현재샤크의 거리가 더 가까우면 더 가까운 물고기를 먹으러가야한다.
beforeShark.x = nx
beforeShark.y = ny
beforeShark.dist = dist + 1
}
if beforeShark.dist == dist + 1{//거리가 같을경우
if beforeShark.x > nx{
beforeShark.x = nx
beforeShark.y = ny
beforeShark.dist = dist + 1
}else if beforeShark.x == nx {
if beforeShark.y > ny {
beforeShark.x = nx
beforeShark.y = ny
beforeShark.dist = dist + 1
}
}
}
}
queue.append(((nx, ny), dist + 1))
visited[nx][ny] = true
}
}
if beforeShark.dist == Int.max{
print(totalDist)
break
}else{
totalDist += beforeShark.dist
arr[beforeShark.x][beforeShark.y] = 0
feed -= 1
if feed == 0 {
size += 1
feed = size
}
}
}
}
bfs(sharkX, sharkY)'Algorithm > 문제풀이_백준' 카테고리의 다른 글
| [Swift][BFS] 백준 10026 (적록색약) (0) | 2022.01.25 |
|---|---|
| [Swift][BFS] 백준 1963번 (소수 경로) (0) | 2022.01.25 |
| [Swift][DFS][BFS] 백준 16947번 (서울 지하철 2호선) (0) | 2022.01.20 |
| [Swift][BFS] 백준 12869번 (뮤탈리스크) (0) | 2022.01.17 |
| [Swift][BruteForce] 백준 16198번 (에너지 모으기) (0) | 2022.01.14 |
댓글