문제
핵심
- 입력의 크기가 이므로 구현에 초점을 맞춘다.
- 뱀 게임을 만드는 문제이다. 뱀이 기어다니면서 사과를 먹으면 길이가 늘어나고 벽 또는 자기 자신과 부딪히면 게임이 끝난다. 추가로 방향 변한 횟수가 주어져 시간이 되면 뱀의 방향을 변환시켜 주어야 한다.
- 뱀의 이동 방향을 고려할 때 머리 부분과 나머지(몸통, 꼬리) 부분을 분리했다. 그 이유는 머리는 시간에 따라 방향이 변화하기에 방향 변수가 필요하지만, 몸통은 머리가 지나갔던 경로를 추가하면 되기 때문이다.
- 문제도 직관적이고 특별히 어려운 부분이 없다고 생각했는데 구현이 잘 안된다. 결국 머리를 쥐어뜯으며 돌아가게만 구현하였다. 초기 기본적인 구현 로직은 다음과 같다.
- 먼저 머리가 이동한다. 머리 위치와 방향을 담기 위한 head 변수를 선언한다.
- 머리가 움직이고 나서 방향 변환 시간이 되었다면 방향 정보를 head 변수에 업데이트한다.
- 머리가 움직인 곳에 사과가 있다면 몸통을 추가하고, 몸통의 크기를 1 증가시킨다.
- 몸통이 있다면(몸통의 크기가 0이 아니라면) 머리가 이동하기 전에 위치를 몸통에 추가하고 기존의 몸통 -1 개를 (머리 부분은 이미 추가했으므로) 몸통에 추가한다.
- 몸통을 추가하며 1을, 제거하며 0으로 바꾸며 상태를 표시했기에 뱀 머리가 움직일 때 자기 몸(1)과 충돌을 파악할 수 있다.
- 처음 코드를 개선하면서 좀 더 효율적인 구현 과정을 아래에 담았다.
개선
while (1) {
++time;
auto [y, x, dir] = head;
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny < 0 || ny >= n || nx < 0 || nx >= n)
break;
if (board[ny][nx] == 1)
break;
if (board[ny][nx] == 2) // 사과가 있다면 몸통 사이즈를 늘린다.
++bodySize;
board[ny][nx] = 1; // 머리가 움직인다.
board[y][x] = 0;
if (!rot.empty() && time == rot.front().first) { // 방향 정보를 갱신한다.
if (rot.front().second == 'D')
dir = (dir + 1) % 4;
else
dir = (dir + 3) % 4;
rot.pop();
}
head = {ny, nx, dir};
queue<pair<int, int>> body;
if (bodySize)
body.push({y, x}); // 몸통을 기존 머리 위치로 추가한다.
int cnt = bodySize - 1; // 몸통에 기존 머리 위치를 추가 했으니 하나를 빼어 이동시킨다.
for (int i = 0; i < cnt; ++i) {
if (!origin.empty()) { // 기존에 몸통이 있다면 cnt만큼 body로 옮겨담는다.
body.push(origin.front());
board[origin.front().first][origin.front().second] = 0;
origin.pop();
}
}
// body에는 한 칸 이동한 뱀의 몸통이 담겨있다. 이를 다시 기존의 몸통으로 옮겨담는다.
while (!origin.empty()) {
auto cur = origin.front();
board[cur.first][cur.second] = 0;
origin.pop();
}
while (!body.empty()) {
auto cur = body.front();
board[cur.first][cur.second] = 1;
body.pop();
origin.push(cur);
}
}- 해당 코드로 통과했지만, 코드에 중복이 많고 복잡하다. 새로운 머리 위치를 뱀의 몸통에 추가하면 구현이 단순해진다. 사과가 없는 경우에 꼬리가 새로운 머리 위치로 가는 것을 구현하면 되는 것이므로 새로운 머리 위치를 몸통에 추가하고, 기존 몸통에 있던 오래된 부분(꼬리)을 제거하면 된다. 코드가 직관적이고 단순해진 것을 볼 수 있다.
while (1) {
++time;
auto [y, x, dir] = head;
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny < 0 || ny >= n || nx < 0 || nx >= n)
break;
if (board[ny][nx] == 1)
break;
if (board[ny][nx] != 2) {
auto [tailY, tailX] = body.front(); body.pop();
board[tailY][tailX] = 0;
}
board[ny][nx] = 1;
body.push({ny, nx});
head = {ny, nx, dir};
if (!rot.empty() && time == rot.front().first) {
if (rot.front().second == 'D')
dir = (dir + 1) % 4;
else
dir = (dir + 3) % 4;
head = {ny, nx, dir};
rot.pop();
}
}코드
시간복잡도
C++
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int board[104][104];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, l;
cin >> n >> k;
for (int i = 0; i < k; ++i) {
int y, x;
cin >> y >> x;
board[y - 1][x - 1] = 2;
}
cin >> l;
queue<pair<int, char>> rot;
for (int i = 0; i < l; ++i) {
int time; char dir;
cin >> time >> dir;
rot.push({time, dir});
}
tuple<int, int, int> head = {0, 0, 1};
board[0][0] = 1;
queue<pair<int, int>> body;
body.push({0, 0});
int time = 0;
while (1) {
++time;
auto [y, x, dir] = head;
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny < 0 || ny >= n || nx < 0 || nx >= n)
break;
if (board[ny][nx] == 1)
break;
if (board[ny][nx] != 2) {
auto [tailY, tailX] = body.front(); body.pop();
board[tailY][tailX] = 0;
}
board[ny][nx] = 1;
body.push({ny, nx});
head = {ny, nx, dir};
if (!rot.empty() && time == rot.front().first) {
if (rot.front().second == 'D')
dir = (dir + 1) % 4;
else
dir = (dir + 3) % 4;
head = {ny, nx, dir};
rot.pop();
}
}
cout << time;
}Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, 1, 0, -1};
static int[][] board = new int[104][104];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
board[y - 1][x - 1] = 2;
}
int l = Integer.parseInt(br.readLine());
Queue<int[]> rot = new LinkedList<>();
for (int i = 0; i < l; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int time = Integer.parseInt(st.nextToken());
int dir = 1;
if (st.nextToken().equals("L"))
dir = -1;
rot.add(new int[]{time, dir});
}
int[] head = new int[]{0, 0, 1};
board[0][0] = 1;
Queue<int[]> body = new LinkedList<>();
body.add(new int[]{0, 0});
int time = 0;
while (true) {
++time;
int y = head[0];
int x = head[1];
int dir = head[2];
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny < 0 || ny >= n || nx < 0 || nx >= n)
break;
if (board[ny][nx] == 1)
break;
if (board[ny][nx] != 2) {
var cur = body.poll();
board[cur[0]][cur[1]] = 0;
}
board[ny][nx] = 1;
body.add(new int[]{ny, nx});
head[0] = ny;
head[1] = nx;
head[2] = dir;
if (!rot.isEmpty() && time == rot.peek()[0]) {
if (rot.peek()[1] == 1)
dir = (dir + 1) % 4;
else
dir = (dir + 3) % 4;
head[2] = dir;
rot.poll();
}
}
System.out.println(time);
}
}
꾸준하게