[Algorithm] BOJ_18809_Gaaaaaaaaaarden - Go

오래간만에 Go를 사용해 통해 알고리즘을 풀어보았다.

감을 살리기 위해 적당한 난이도처럼 보이는 구현 문제를 건드려보았는데.. 쒯..

내가 너무 어렵게 생각했을 수도 있지만 정말 다양한 것들을 엮어서 푼 것 같다.(뿌듯함 :D)

문제 링크

BOJ_18809_Gaaaaaaaaaarden

코드

package main

import (
    "bufio"
    "fmt"
    "os"
)

type queue struct {
    data []pos
}

type pos struct {
    x, y int
}

func (q *queue) pop() pos {
    if len(q.data) == 0 {
        return pos{}
    }
    val := q.data[0]
    q.data = q.data[1:]
    return val
}

func (q *queue) push(val pos) {
    q.data = append(q.data, val)
}

func (q queue) isEmpty() bool {
    return len(q.data) == 0
}

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

var originGarden [][]int
var copyGarden [][]int

var q queue

var waterPos []pos // garden에서 값이 2인 위치 == 배양액이 시작될 수 있는 위치
var visited [][]int
var grCombs [][]int 
var startPosCombs [][]pos // G와 R중 숫자가 적은것을 1
var N, M, G, R int
var tmpPos []pos
var tmpInt []int
var ansTmp int
var max int

func main() {
    r := bufio.NewReader(os.Stdin)
    fmt.Fscan(r, &N, &M, &G, &R)
    if R < G {
        G, R = R, G
    }
    originGarden = make([][]int, N)
    for i := 0; i < N; i++ {
        originGarden[i] = make([]int, M)
    }
    for y := 0; y < N; y++ {
        for x := 0; x < M; x++ {
            fmt.Fscan(r, &originGarden[y][x])
            if originGarden[y][x] == 2 {
                waterPos = append(waterPos, pos{x: x, y: y})
                originGarden[y][x] = 1
            }
        }
    }
    tmpPos = make([]pos, G+R)
    makeCombPos(G+R, 0, 0)
    tmpInt = make([]int, G)
    makeCombInt(G, 0, 0)
    start()
    fmt.Println(max)
}

func makeCombPos(purpose, index, count int) {
    if purpose == count {
        tmp := make([]pos, purpose)
        copy(tmp, tmpPos)
        startPosCombs = append(startPosCombs, tmp)

        return
    }
    for i := index; i < len(waterPos); i++ {
        tmpPos[count] = waterPos[i]
        count++
        makeCombPos(purpose, i+1, count)
        count--
    }
}

func makeCombInt(purpose, index, count int) {
    if purpose == count {
        tmp := make([]int, 0)
        tmp = append(tmp, tmpInt...)
        grCombs = append(grCombs, tmp)
        return
    }
    for i := index; i < G+R; i++ {
        tmpInt[count] = i
        count++
        makeCombInt(purpose, i+1, count)
        count--
    }
}

func start() {
    for _, gardenPos := range startPosCombs {
        for _, colorIdx := range grCombs {
            ansTmp = 0
            copyGarden = make([][]int, N)
            for i := 0; i < N; i++ {
                copyGarden[i] = append(copyGarden[i], originGarden[i]...)
            }
            visited = make([][]int, N)
            for i := 0; i < N; i++ {
                visited[i] = make([]int, M)
            }
            cnt := 0
            for i := 0; i < len(gardenPos); i++ {
                if cnt < len(colorIdx) {
                    if i == colorIdx[cnt] {
                        copyGarden[gardenPos[i].y][gardenPos[i].x] = 7
                        cnt++
                        q.push(gardenPos[i])
                        visited[gardenPos[i].y][gardenPos[i].x] = 1

                        continue
                    }
                }
                copyGarden[gardenPos[i].y][gardenPos[i].x] = 8
                visited[gardenPos[i].y][gardenPos[i].x] = 1

                q.push(gardenPos[i])
            }
            next()
        }
    }
}

func next() {
    for !q.isEmpty() {
        n := q.pop()
        if copyGarden[n.y][n.x] == 9 {
            continue
        }
        for k := 0; k < 4; k++ {
            nextX := n.x + dx[k]
            nextY := n.y + dy[k]
            if isRange(pos{x: nextX, y: nextY}) {
                if copyGarden[n.y][n.x] == 7 {
                    if copyGarden[nextY][nextX] == 1 {
                        visited[nextY][nextX] = visited[n.y][n.x] + 1
                        copyGarden[nextY][nextX] = 7
                        q.push(pos{x: nextX, y: nextY})
                    } else if copyGarden[nextY][nextX] == 8 && visited[nextY][nextX] == visited[n.y][n.x]+1 {
                        ansTmp++
                        copyGarden[nextY][nextX] = 9

                    }
                } else if copyGarden[n.y][n.x] == 8 {
                    if copyGarden[nextY][nextX] == 1 {
                        visited[nextY][nextX] = visited[n.y][n.x] + 1
                        copyGarden[nextY][nextX] = 8
                        q.push(pos{x: nextX, y: nextY})
                    } else if copyGarden[nextY][nextX] == 7 && visited[nextY][nextX] == visited[n.y][n.x]+1 {
                        ansTmp++
                        copyGarden[nextY][nextX] = 9
                    }
                }

            }
        }
    }

    if max < ansTmp {
        max = ansTmp
    }
}

func isRange(p pos) bool {
    return p.y >= 0 && p.y < N && p.x >= 0 && p.x < M
}

간단한 설명

크게는 bfs를 사용하여 풀었다.
그렇지만 내가 생각하기에 이 문제의 핵심은 배양액을 어떻게 뿌릴 것이냐 였다.

어떻게 설명해야 할지 잘 모르겠는데..

배양액을 뿌릴 곳에 대한 후보 조합, 배양액의 색을 정하는 조합 두 가지 조합을 뽑고.. place holder 개념으로다가... 흐음.. 어떻게 설명해야 할지 막막하다. 잠시만 기다려 달라. 이럴 땐 그림을 그리는 게 제일 확실하겠다.

예시

노란색 땅에 초록색 배양액 2개와 빨간색 배양액 1개를 뿌려야 한다고 하자.

이렇게 말하는 게 맞을지 모르겠는데 place holder라고 생각하며 풀었다.

총 세 개의 배양액을 5개의 구역에 뿌릴 수 있다. 그래서 일단 5개의 구역 중 3개의 구역(배양액의 총 개수)을 뽑는 순서가 없는 조합 makeCombPos 함수를 작성했다.

결과

이런 식으로 되겠다.

5C3 이니 이 예시에선 총 10개가 나오겠다.

다음은 배양액을 살펴보자.

순서가 없으니 3C1. 즉, 총 3개가 나오겠다.

그럼 총 가짓수는 10*3 30개이다.

이 30가지의 경우에 bfs를 사용하여 꽃이 가장 많이 피는 경우를 찾았다.

그리고

결과

한방에 뽞!! 뿌드읏!!

끗!

아구구 오랜만에 알고리즘 풀려니까 힘드네..