[Algorithm]BOJ_16234_인구이동_Go

문제 링크

BOJ 16234 인구 이동

풀이 방법

1. bfs를 통해 국경선을 개방해야하는 나라를 탐색
2. 국경선을 개방해야 할 나라끼리 그룹을 나누어 slice에 저장
3. 인구 이동
4. 날짜 추가
5. 1 ~ 5 반복

package q16234

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
)

type country struct {
    x          int
    y          int
    population int
}

type pos struct {
    x int
    y int
}

var countryStatus [][]*country
var visited [][]bool
var openCountryGroup [][]*country

var dx = [4]int{-1, 0, 1, 0}
var dy = [4]int{0, -1, 0, 1}

var N, L, R int
var queue []pos

var groupNum int

func bfsForOpenCountry(groupNum int) {
    for len(queue) != 0 {
        nowX := queue[0].x
        nowY := queue[0].y
        queue = queue[1:]

        for k := 0; k < 4; k++ {
            nextX := nowX + dx[k]
            nextY := nowY + dy[k]
            if posRange(nextX, nextY) && visited[nextX][nextY] == false {
                if isNeedOpen(countryStatus[nowX][nowY].population, countryStatus[nextX][nextY].population) {
                    visited[nextX][nextY] = true
                    queue = append(queue, pos{nextX, nextY})
                    openCountryGroup[groupNum] = append(openCountryGroup[groupNum], countryStatus[nextX][nextY])
                }
            }
        }
    }
}

func isNeedOpen(first, second int) bool {
    tmp := int(math.Abs(float64(first) - float64(second)))
    if tmp >= L && tmp <= R {
        return true
    }
    return false
}

func populationMove() {
    for i := 0; i < len(openCountryGroup); i++ {
        sum := 0
        for _, c := range openCountryGroup[i] {
            sum += c.population
        }
        val := int(sum / len(openCountryGroup[i]))
        for _, c := range openCountryGroup[i] {
            c.population = val
        }
    }
}

func initAlgo() {
    visited = make([][]bool, N)
    groupNum = 0
    for i := range countryStatus {
        visited[i] = make([]bool, N)
    }
    for i := range countryStatus {
        for j := range countryStatus {
            visited[i][j] = false
        }
    }
    openCountryGroup = make([][]*country, 0)
}

func posRange(x, y int) bool {
    if x >= 0 && x < N && y >= 0 && y < N {
        return true
    }
    return false
}

func stringToInt(a string) int { 
    val, _ := strconv.Atoi(a)
    return val
}

func Start() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    fmt.Scan(&N, &L, &R)
    countryStatus = make([][]*country, N)
    for i := range countryStatus {
        countryStatus[i] = make([]*country, N)
    }
    for y := 0; y < N; y++ {
        for x := 0; x < N; x++ {
            scanner.Scan()
            countryStatus[x][y] = &country{x, y, stringToInt(scanner.Text())}
        }
    }
    day := 0
    for {
        initAlgo()
        for y := 0; y < N; y++ {
            for x := 0; x < N; x++ {
                if visited[x][y] == false {
                    queue = append(queue, pos{x, y})
                    visited[x][y] = true
                    openCountryGroup = append(openCountryGroup, make([]*country, 0))
                    openCountryGroup[groupNum] = append(openCountryGroup[groupNum], countryStatus[x][y])
                    bfsForOpenCountry(groupNum)
                    groupNum++
                }
            }
        }
        populationMove()
        if len(openCountryGroup) == N*N {
            break
        }
        day++
    }
    fmt.Println(day)
}

Go를 통해 알고리즘 풀이를 진행하면서 기존에 풀이에 급급했던 알고리즘 습관을 코드를 가독성 좋게 만드는 연습을 진행하고 있다.
확실히 디버깅을 진행함에 있어서 버그를 찾기 편하고 내 코드를 조금 더 아낄 수 있는 습관인 듯 하다. 이러한 습관을 더욱 굳게 다져 나갈 필요가 있겠다.