뱀
문제: 뱀 (백준 3190번)Permalink
구조 분석Permalink
해당 문제는 단순 구현 문제이다. 보드에 사과의 위치를 입력 받고 뱀을 움직이며 조건에 따라 게임을 중단하는 간단한 형태의 문제이나 구현하는데 있어서 생각할 조건이 많고 까다로워 풀이를 할 때 헷갈리지 않게 잘 해야 한다.
풀이 방법Permalink
우선 사과 위치를 표기할 보드와 뱀의 위치를 표기할 보드 두개를 생성한다. 이후 뱀을 구현하기 위해 deque를 사용한다.
Deque를 사용하는 이유는 해당 stl은 push_front, push_back, pop_front, pop_back을 지원하기 때문이다. 이를 활용하면 뱀의 움직임을 더 쉽고 효율적으로 구현할 수 있다.
다음으로 시간별 방향설정을 구현하기 위해 char형 배열을 생성한다. 여기서 굳이 배열을 생성한 이유는 시간을 index로 이용하여 바로 해당 시간의 char가 무엇인지 바로 알 수 있기 때문이다.
마지막으로 방향설정을 하기 위해 dx[4] = {0,1,0,-1}과 dy[4] = {1,0,-1,0}을 전역변수에 생성한다. dx와 dy는 임의로 이름을 붙인 것이고 본인 편한대로 이름을 붙여주면 된다. 여기서 위와 같이 설정한 이유는 인덱스를 이용해 시계방향과 반시계방향을 정할 수 있기 때문이다.
i=0: 오른쪽 진행
i=1: 아래로 진행
i=2: 왼쪽 진행
i=3: 위로 진행
때문에 i를 증가시키면 시계방향 회전 i를 감소시키면 반시계방향 회전한다.
코드Permalink
#include <stdio.h>
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
int n, k, l;
int map[101][101];
int snake[101][101];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
char swift[10001];
deque<pair<int,int>> S;
int main() {
cin >> n;
cin >> k;
for (int i=0; i<k; i++) {
int r, c;
cin >> r >> c;
map[r][c] = 1;
}
cin >> l;
for (int i=0; i<l; i++) {
int t;
char c;
cin >> t >> c;
swift[t] = c;
}
S.push_back({1,1});
snake[1][1] = 1;
int time = 0;
int dir = 0;
while(true) {
time++;
int nc = S.front().first + dx[dir];
int nr = S.front().second + dy[dir];
if (nc < 1 || nc > n || nr < 1 || nr > n) {
break;
}
S.push_front({nc,nr});
if (swift[time] == 'D') {
dir += 1;
if (dir == 4) dir = 0;
}
else if (swift[time] == 'L') {
dir -= 1;
if (dir == -1) dir = 3;
}
if (map[nc][nr] == 1) {
map[nc][nr] = 0;
}
else {
if (snake[nc][nr] == 1) break;
snake[S.back().first][S.back().second] = 0;
S.pop_back();
}
if (snake[nc][nr] == 1) break;
else snake[nc][nr] = 1;
}
cout << time << "\n";
return 0;
}
정리Permalink
해당 문제는 단순 구현 문제였다. 그러나 단순 구현일수록 구현하는게 더 까다롭고 생각할 조건이 많다. 따라서 단순 구현 문제의 경우 문제를 많이 풀면서 자신감을 갖는게 중요하다고 생각한다. 또한 deque stl을 이용하여 여러 문제들을 쉽게 푸는 것을 익혀두면 좋을 것 같다.
댓글남기기