[Algorithm]Programmers_월간코드챌린지_86052_빛의 경로 사이클_Go

링크

링크 : 빛의 경로 사이클

풀이 방법

문제 설명

1. 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
2. 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
3. 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
4. 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

생각해야 할 것

1. 주어진 칸을 생각하며 간단히 좌회전, 우회전을 할 방법을 생각해 낸다.
   • 0 : 위, 1 : 오른쪽, 2 : 아랫쪽, 3 : 왼쪽 으로 지정하여 기존의 방향에서 우회전일 경우 +1, 좌회전일 경우 -1을 해 방향을 지정해 준다.
2. 격자의 범위를 지나칠 때 반대쪽에서 다시 나타나는 방법을 생각해 낸다.
   • position struct를 만들어 receive함수를 통해 항상 이를 체크한다.
3. 빛이 이전과 같은 위치, 방향으로 진행하면 결국 같은 사이클을 만들 것임을 인지한다.
4. 모든 가능성을 확인하여야 한다.

package q86052

import (
    "sort"
)

var rowSize int
var colSize int
var globalMap []string
var check map[light]struct{}

type position struct {
    row, col int
}

func (p *position) getRightPosition() {
    if p.row == -1 {
        p.row = rowSize - 1
    }
    if p.row == rowSize {
        p.row = 0
    }
    if p.col == -1 {
        p.col = colSize - 1
    }
    if p.col == colSize {
        p.col = 0
    }
}

type light struct {
    pos position
    dir int // 0 위, 1 오른쪽, 2 아래, 3 왼쪽
}

func (l light) getNextLight() light {
    nextRow := l.pos.row
    nextCol := l.pos.col
    nextDir := l.dir
    switch l.dir {
    case 0:
        nextRow -= 1
    case 1:
        nextCol += 1
    case 2:
        nextRow += 1
    case 3:
        nextCol -= 1
    }

    pos := position{
        row: nextRow,
        col: nextCol,
    }
    pos.getRightPosition()
    switch globalMap[pos.row][pos.col] {
    case 'L':
        nextDir--
    case 'R':
        nextDir++
    case 'S':

    }

    if nextDir == -1 {
        nextDir = 3
    }
    if nextDir == 4 {
        nextDir = 0
    }

    return light{
        pos,
        nextDir,
    }

}

var footPrints [][]light
var idx int

func findSameLight(footPrints []light, indexMap map[light]int, aLight light) int {
    if _, ok := indexMap[aLight]; ok {
        return indexMap[aLight]
    }
    check[aLight] = struct{}{}

    indexMap[aLight] = idx
    idx++
    return -1
}

func solution(grid []string) []int {
    var answer []int
    globalMap = grid
    rowSize = len(grid)
    colSize = len(grid[0])
    check = make(map[light]struct{})
    index := 0
    for r := 0; r < rowSize; r++ {
        for c := 0; c < colSize; c++ {
            for d := 0; d < 4; d++ {

                if _, ok := check[light{pos: position{row: r, col: c}, dir: d}]; ok {
                    continue
                }
                footPrints = append(footPrints, make([]light, 0))
                footPrints[index] = append(footPrints[index], light{pos: position{row: r, col: c}, dir: d})
                idx = 0
                indexMap := make(map[light]int)
                for {
                    nextLight := footPrints[index][len(footPrints[index])-1].getNextLight()
                    val := findSameLight(footPrints[index], indexMap, nextLight)
                    if val == -1 {
                        footPrints[index] = append(footPrints[index], nextLight)
                    } else {
                        answer = append(answer, len(footPrints[index])-1)
                        check[nextLight] = struct{}{}
                        break
                    }
                }
                index++
            }
        }
    }

    sort.Ints(answer)
    return answer
}

func Start() {
    grid := []string{"SL", "LR"}
    solution(grid)
}

코드 설명

• 모든 격자의 위치와 그 위치에서의 방향을 생각하기 위해 삼중 반복문을 수행하였다.
• GoLang은 Set이 따로 없기에 map을 Set처럼 활용하여 이전에 같은 빛의 움직임이 있었는지 확인하고 있었다면 그 이후는 생각하지 않는다. 만약 사이클이 생겼다면 이전에 체크가 됐을테고 그렇다면 다시 확인할 필요는 없다.
• indexMap을 통해 진행 중인 사이클에서 같은 빛의 속성을 가진 빛이 있었을 때 끄 속성이 몇번 째에 나왔는지 파악한다.(이 부분을 하지 않으니 7번 테스트케이스에서 시간 초과가 났다.)
• 오름차순으로 정렬하여 answer slice에 넣어준다.

마무리.

아... 긴 한주였다. 진짜 좋은 경험을 하였지만 아쉬움이 많이 남는다. 나의 공부가 부족했던 탓이다. 더 열심히하자. 기죽지말자.