3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
https://www.acmicpc.net/problem/3190
문제
문제 해결을 위한 과정
가장 먼저 주의해야 할 점은 보드의 맨 위 좌측의 좌표가 0행 0열이 아닌 1행 1열이라는 점입니다. 따라서 사과의 위치를 입력을 받은 후 일반적으로 사용하는 행, 열의 위치에 사과를 저장하기 위해 입력된 좌표에서 각각 1씩 빼서 보드에 사과를 집어넣어야 합니다. 단순하게 문제의 조건을 따라만 가면 그다지 어려운 문제는 아닙니다. 뱀이 바라보는 방향을 기준으로 한 칸씩 이동을 하게 되는데 몸길이가 늘려 머리가 다음칸에 가게 됩니다. 다음칸이 벽이거나 꼬리가 있는 부분이 아닌 한 머리가 속한 칸이 사과가 없는 칸이면 꼬리가 한 칸 앞으로 이동을 해야 합니다. 따라서 뱀이 현재 위치한 좌표들로 리스트를 만든 후 뱀이 머리가 닿는 부분을 리스트에 append 하게 되면 반대로 꼬리의 부분은 리스트의 맨 앞부분일 것입니다. 따라서 해당 리스트의 맨 앞을 pop 해주게 되면 쉽게 꼬리를 한 칸 앞으로 이동해줄 수 있습니다. 비록 리스트의 pop이 O(N)의 시간 복잡도를 가지더라도 이 문제에서는 통과할 수 있습니다.
문제 해결을 위한 팁
이 문제를 풀때 신경 써야 할 부분은 바로 방향에 관한 부분입니다. 보통 방향에 관한 부분이 문제에서 나오면 dx, dy로 각각의 방향 리스트를 만드는 것이 일반적입니다. 맨 처음 뱀이 바라보고 있는 부분이 오른쪽 즉 동쪽이기 때문에 동쪽을 리스트의 0번째 리스트로 입력을 한 후 반 시계 방향으로 동쪽, 북쪽, 서쪽, 남쪽으로 방향을 설정하면 dx, dy는 다음과 같습니다.
dx = [0, -1, 0, 1]
dy = [1, 0, -,1 0]
이 좌표는 수학적 의미의 x, y좌표가 아닌 프로그래밍에서의 행, 열의 의미입니다. 동쪽 즉 오른쪽으로 움직이는 경우 행은 그대로지만 열이 하나 증가하기 때문에 dx, dy의 0번째 인덱스가 0, 1 입니다. 이렇게 하면 기존의 좌표를 x, y 다음 과표를 nx, ny라 지정하면
nx = x + dx[0]
ny = y + dy[0]
이처럼 지정할 수 있습니다. 이번엔 표를 보고 생각해봅시다.
| 방향(리스트에서의 인덱스 값) | D 인 경우(리스트에서의 인덱스 값) | L 인 경우(리스트에서의 인덱스 값) |
| 동쪽(0) | 남쪽(3) | 북쪽(1) |
| 북쪽(1) | 동쪽(0) | 서쪽(2) |
| 서쪽(2) | 북쪽(1) | 남쪽(3) |
| 남쪽(3) | 서쪽(2) | 동쪽(0) |
위 표를 보고 기존 방향이 dir일 경우 다음과 같음을 알 수 있습니다.
D인 경우 dir = (dir - 1) % 4
L인 경우 dir = (dir + 1) % 4
소스코드 - python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
N = int(input())
graph = [[0]*N for _ in range(N)]
apple = int(input())
movement = []
for i in range(apple):
a, b = map(int, input().split())
graph[a-1][b-1] = 1 # 문제에서 맨 좌측 위가 1, 1 이라고 하였기 때문
move = int(input())
for i in range(move):
a, b = input().split()
movement.append((int(a), b))
# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
def turn(dir, x): # 다음 방향을 정하는 함수
if x == 'D':
dir = (dir -1) % 4
elif x == 'L':
dir = (dir+1) % 4
return dir
def game():
x = 0; y = 0
graph[x][y] = 2 # 맨 처음 뱀이 0, 0 에 있으므로 해당 지역을 뱀이 있는것으로 표시
snake = [(x, y)] # 뱀의 현재 좌표를 담는 리스트
count = 0
dir = 0 # 맨 처음 방향인 동쪽을 0으로 설정
index = 0
while True:
nx = x + dx[dir]
ny = y + dy[dir]
if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] != 2: # 벽이 아니거나 뱀이 있는 지역이
if graph[nx][ny] == 0: # 사과 없는 지역인 경우
count += 1
graph[nx][ny] = 2
snake.append((nx, ny))
prev_x, prev_y = snake.pop(0)
graph[prev_x][prev_y] = 0
elif graph[nx][ny] == 1: #사과 있는 지역
count += 1
graph[nx][ny] = 2
snake.append((nx, ny))
if index < move and count == movement[index][0]:
dir = turn(dir, movement[index][1])
index += 1
x = nx
y = ny
else:
return count
print(game()+1)
|
cs |
소스코드 - c++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#include <bits/stdc++.h>
#define MAX 101
using namespace std;
int n, k;
int graph[MAX][MAX];
int l;
queue<pair<int, char>> dir;
queue<pair<int, int>> snake;
int direction;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int moveDirection(int direction, char dInfo) {
if (direction == 0) {
if (dInfo == 'L')
return 2;
else
return 3;
}
else if (direction == 1) {
if (dInfo == 'L')
return 3;
else
return 2;
}
else if (direction == 2) {
if (dInfo == 'L')
return 1;
else
return 0;
}
else {
if (dInfo == 'L')
return 0;
else
return 1;
}
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
cin >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
graph[a - 1][b - 1] = 1;
}
cin >> l;
for (int i = 0; i < l; i++) {
int a;
char c;
cin >> a >> c;
dir.push(make_pair(a, c));
}
int time = 1;
direction = 3;
int xPos = 0, yPos = 0;
graph[xPos][yPos] = 2;
snake.push(make_pair(xPos, yPos));
int tInfo = dir.front().first;
char dInfo = dir.front().second;
dir.pop();
while (true) {
xPos += dx[direction];
yPos += dy[direction];
if (xPos < 0 || yPos < 0 || xPos >= n || yPos >= n) {
break;
}
if (graph[xPos][yPos] == 2) {
break;
}
snake.push(make_pair(xPos, yPos));
if (graph[xPos][yPos] != 1) { // 사과없는 경우
int x = snake.front().first;
int y = snake.front().second;
graph[x][y] = 0;
snake.pop();
}
if (graph[xPos][yPos] == 0) { // 사과 있는 경우
graph[xPos][yPos] = 0;
}
graph[xPos][yPos] = 2;
if (time == tInfo) {
direction = moveDirection(direction, dInfo);
if (!dir.empty()) {
tInfo = dir.front().first;
dInfo = dir.front().second;
dir.pop();
}
}
time++;
}
cout << time;
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 18352: 특정 거리의 도시 찾기(Python) (0) | 2020.12.04 |
|---|---|
| 백준 알고리즘 15686: 치킨 배달 (Python) (0) | 2020.11.30 |
| 백준 알고리즘 1914: 하노이 탑 (0) | 2020.11.28 |
| 백준 알고리즘 18406: 럭키 스트레이트 (Python) (0) | 2020.11.27 |
| 백준 알고리즘 1439: 뒤집기 (Python) (0) | 2020.11.25 |