백준 아기상어 (Go)

문제 링크: www.acmicpc.net/problem/16236

16236번: 아기 상어

 

삼성 기출문제로 꽤 까다로운 문제입니다. 문제를 보면 다들 BFS로 풀어야 한단건 느끼셨을 겁니다.

문제 조건을 보면 거리가 같은 경우 위쪽을 먼저 탐색해야하고 위쪽에 여러개 있는 경우 제일 왼쪽을 탐색해야한다고 나와있습니다.

그래서 dx = (-1, 0, 1, 0)  dy = (0, -1, 0, 1) 이런식으로 위쪽, 왼쪽을 먼저 BFS탐색으로 풀면 되지 않을까라는 생각이 들 수 있습니다.

그러나 위 방식을 이용하여 풀면 틀리게 됩니다.

5 x 5 배열이 있고 (2, 2)부터 아기상어가 시작한다고 할 때 거리가 2인 지점들을 위처럼 BFS방식을 사용해서 탐색하면 순서가 아래와 같습니다.

?  ?  1  ?  ?
?  2  x  3  ?
4  x  S  x  6
?  5  x  7  ?
?  ?  8  ?  ?

모두 거리가 2로 같으므로 위쪽, 왼쪽을 먼저 탐색해야하지만 위 그림을 보면 탐색 순서가 맞지 않습니다.

그러므로 문제를 풀기 위해서는 현재 위치에서 BFS탐색을 하여 잡아먹을 수 있는 물고기들을 모두 알아내고 그 물고기들을 거리와 x좌표(위쪽) y좌표(왼쪽)을 heap에 넣어서 그 기준을 토대로 다음 위치를 정해야 합니다. (또는 그냥 리스트에 넣고 나중에 정렬을 해도 됩니다.)

아래는 Go 코드입니다.

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)
 
type Item struct {
    dist int
    x      int
    y    int
}
 
 
type Queue []*Item // bfs탐색시 사용할 큐 
 
func (q *Queue) Push(shark *Item) {
    *q = append(*q, shark)
}
 
func (q *Queue) Pop() *Item {
    old := *q
    n := len(old)
    popped := old[0]
    old[0] = nil
    *q = old[1:n]
    return popped
}
 
var n int  // input에서 처음 받는 n
var dx = [4]int{0, 0, -1, 1}
var dy = [4]int{-1, 1, 0, 0}
 
func Bfs(board [][]int, startX, startY, startSize int) *Item {
    visited := make([][]int, n) // 방문 중복방지용
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            visited[i] = append(visited[i], 0)
        }
    }
 
    
    var fish []*Item  // 잡아먹을 수 있는 물고기들
    q := Queue{}
    q.Push(&Item{0, startX, startY})
    visited[startX][startY] = 1
 
    for {
        if len(q) == 0 { break }
        info := q.Pop()
        x, y, dist := info.x, info.y, info.dist
 
        for i:=0; i<4; i++ {
            nx, ny := x+dx[i], y+dy[i]
            if 0<=nx && nx<n && 0<=ny && ny<n && visited[nx][ny] == 0 {
                if board[nx][ny] != 0 && startSize > board[nx][ny] { // 잡아 먹을 수 있는 경우
                    fish = append(fish, &Item{dist+1, nx, ny})
                    visited[nx][ny] = 1
                } else if startSize == board[nx][ny] || board[nx][ny] == 0 {
                    q.Push(&Item{dist+1, nx, ny})
                    visited[nx][ny] = 1
                }
            }
        }
    }
    
    if len(fish) == 0 {  // nil이 반환되면 더이상 잡아먹을 물고기가 없다는 뜻
        return nil
    }
 
    sort.Slice(fish, func(i, j int) bool {  // dist -> 위쪽 -> 왼쪽 순서로 정렬
        if fish[i].dist == fish[j].dist {
            if fish[i].x == fish[j].x {
                return fish[i].y < fish[j].y
            } else {
                return fish[i].x < fish[j].x
            }
        }
        return fish[i].dist < fish[j].dist
    })
 
    return fish[0]
}
 
 
func main() {
    fmt.Scanln(&n)
 
    board := make([][]int, n)
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
 
    var startX, startY int // 처음 아기상어 위치
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            scanner.Scan()
            num, _ := strconv.Atoi(scanner.Text())
            board[i] = append(board[i], num)
            if num == 9 {
                startX, startY = i, j
            }
        }
    }
 
    answer := 0
    size, eaten := 2, 0
 
    for {
        board[startX][startY] = 0  // 시작지점은 0으로 바꿔줌
        info := Bfs(board, startX, startY, size)
 
        if info == nil {
            fmt.Println(answer)
            break
        }
 
        dist, x, y := info.dist, info.x, info.y
        
        eaten += 1
        if size == eaten {
            size += 1
            eaten = 0
        }
 
        startX, startY = x, y
        answer += dist
    }
 
}

 

파이썬의 collections.deque 같은 내장 모듈이 없어서 큐를 직접 구현한 것도 있고 전체적으로 코드가 좀 깁니다. 채점시에 20ms정도가 나옵니다.