백준 3190번 - 뱀 (Go)

https://www.acmicpc.net/problem/3190

분석

이 문제는 시뮬레이션을 구현하면 되는 문제입니다. 하지만 뱀의 상태를 Deque 를 사용하여 관리하는게 키 포인트 였습니다.

시간 복잡도는 2 <= n <= 100 이고, 0 <= k <= 100 이므로 최대 O(n^2) = 10,000 으로 여유롭습니다.

공간 복잡도는 2차원 배열 탐색 int형 O(n^2) = 8byte * 101^2 = 약 80,000 뱀의 상태 16byte * 101^2 = 약 160,000 을 더하면 24KB 로 여유롭습니다.

 

알고리즘을 생각해보면,

 

1. 뱀의 이동:
   • 매 초마다 머리를 다음 칸으로 이동시킵니다.
   • 벽이나 자기 자신의 몸에 부딪히면 게임이 종료됩니다.
   • 사과가 있다면: 꼬리는 그대로 두고 머리만 추가합니다.
   • 사과가 없다면: 머리를 추가하고, 가장 오래된 좌표(꼬리)를 제거합니다.
2. 방향 전환:
   • 특정 초가 지났을 때 L(왼쪽 90도) 혹은 D(오른쪽 90도)로 회전합니다.
   • 상(0), 우(1), 하(2), 좌(3) 순서로 방향 벡터를 설정하면, D는 (dir + 1) % 4, L은 (dir + 3) % 4로 쉽게 계산할 수 있습니다.

 

풀이 코드

package main

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

type Point struct {
	x, y int
}

type Move struct {
	sec int
	dir string
}

var (
	n, k int
	dx = []int{-1, 0, 1, 0}
	dy = []int{0, 1, 0, -1}
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	fmt.Fscan(in, &n, &k)

	grid := make([][]int, n + 1)
	for i := range grid {
		grid[i] = make([]int, n + 1)
	}

	for i := 0; i < k; i++ {
		var x, y int

		fmt.Fscan(in, &x, &y)
		grid[x][y] = 1
	}

	var l int
	fmt.Fscan(in, &l)
	moves := make([]Move, l)
	for i := 0; i < l; i++ {
		fmt.Fscan(in, &moves[i].sec, &moves[i].dir)
	}

	snake := []Point{{1, 1}}
	grid[1][1] = 2
	curDir := 1
	time := 0
	moveIdx := 0

	for {
		time++

		head := snake[len(snake) - 1]
		nx, ny := head.x + dx[curDir], head.y + dy[curDir]

		if nx < 1 || nx > n || ny < 1 || ny > n || grid[nx][ny] == 2 {
			break
		}

		if grid[nx][ny] != 1 {
			tail := snake[0]
			grid[tail.x][tail.y] = 0
			snake = snake[1:]
		}

		grid[nx][ny] = 2
		snake = append(snake, Point{nx, ny})

		if moveIdx < l && moves[moveIdx].sec == time {
			if moves[moveIdx].dir == "D" {
				curDir = (curDir + 1) % 4
			} else {
				curDir = (curDir + 3) % 4
			}

			moveIdx++
		}
	}

	fmt.Fprintln(out, time)
}

회고

뱀의 상태를 duque 로 관리한다는 아이디어가 생각해내기 어려운 것 같습니다.

앞으로 문제 분석을 더 구체화 하며 푸는 습관이 중요할 것 같습니다.