[C++] 3190 : 뱀
#include <iostream>
#include <utility> // pair
#include <deque>
using namespace std;
int board[101][101] = {0}; //보드 0 : 빈칸, 1 : 사과, 2 : 뱀
char timeBoard[10001] = {0}; // 시간 저장 배열
int N, K, L;
int X; char C;
int sec = 0; // 0초
deque<pair<int, int> > snake; // 꼬리 머리 둘 다 줄고 늘 수 있음
int d = 0; // 현재 뱀이 바라보고 있는 방향, 처음엔 오른쪽
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };
int nx, ny;
int main(int argc, char **argv){
int x, y;
scanf("%d %d",&N,&K); // 보드 크기, 사과 개수
for(int i=0; i<K; i++){ // 사과의 위치
scanf("%d %d", &x, &y);
board[x][y] = 1; // 사과 있으면 1
}
snake.push_back(make_pair(1, 1)); // 뱀 (1,1)
board[1][1] = 2; // 뱀 위치 표시
scanf("%d", &L); //뱀의 방향 전환 정보
for(int i = 0; i < L; i++){
scanf("%d %c", &X, &C);
timeBoard[X] = C;
}
while(1){
if(timeBoard[sec] == 'L'){ // 왼쪽으로 90도 회전
d = (d + 1) % 4;
} else if(timeBoard[sec] == 'D'){ // 오른쪽으로 90도 회전
d = (d + 3) % 4;
}
// <1번 조건> : 몸 길이를 늘려 머리를 다음 칸에 위치시킨다.
nx = snake.front().first + dx[d];
ny = snake.front().second + dy[d];
//printf("%d d : %d nx : %d ny : %d\n", sec+1, d, nx, ny);
// 벽에 부딪히거나 몸통에 닿을 경우 - 종료 조건
if(nx < 1 || ny < 1 || nx > N || ny > N || board[nx][ny] == 2){
sec++;
break;
}
snake.push_front(make_pair(nx, ny)); // 머리 길어짐
// <2번 조건> : 이동한 칸에 사과가 있다면 사과가 없어지고 꼬리는 움직이지 않는다.
if(board[nx][ny] == 1){ // 사과가 있는 경우
board[nx][ny] = 2; // 머리 - 뱀이 위치
} else {
// <3번 조건> : 사과가 없다면 몸길이를 줄여서 꼬리가 위치한 칸 비워줌.
board[nx][ny] = 2; // 머리 - 뱀이 위치
board[snake.back().first][snake.back().second] = 0; // 빈칸
snake.pop_back(); // 꼬리 줄이기
}
// for(int i=1; i<=N; i++){
// for(int j=1; j<=N; j++){
// printf("%d ", board[i][j]);
// }
// printf("\n");
// }
sec++; // 1초 흐름
}
printf("%d", sec);
return 0;
}
해냈다 평생의 숙원!!
-
(x, y)는 우리가 수학적으로 생각하는 좌표와는 반대다. 열이 x, 행이 y이다. 앞으로 변수를 y, x 바꾸어 선언하여 혼동을 줄이는 것이 좋겠다.
-
뱀의 위치를 따로 저장하는 배열을 만들기보다는 다른 정수로 표시하여 한 번에 처리하였다.
-
뱀의 마지막 위치를 구하기 위하여 덱을 사용하였다. 모든 뱀의 좌표를 덱에 넣고 push와 pop을 하면서 뱀의 크기를 늘리고 줄일 수 있다. 이건 내가 생각해내지 못하고 알고리즘 분류와 인터넷 검색을 조금 사용하였다...
-
방향 전환에서 0, 1, 2, 3 ... 순서로 증가하면 d = (d+1)% 4
0, 3, 2, 1, 0 ... 순서로 변하면 d = (d+3) % 4이다. 저번 풀이에서 공부한 것을 응용하여 적용시켰다.
주석 처리한 부분은 디버깅 확인용으로 눈으로 확인해보려고 작성한 반복문이다.
아마 한 달 전부터 풀어보려고 손만 댔었던 문제인데 그 때는 인터넷의 풀이글을 읽어도 전혀 이해가 되지 않았다... 역시 쉬운 문제부터 순서대로 풀어보면서 시뮬레이션에 적응하는 것이 중요했던 것 같다. 이제는 그래도 조금 풀어볼 것 같은 정도. 뿌듯하다 발전하고 있구나.
Author And Source
이 문제에 관하여([C++] 3190 : 뱀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-3190-뱀저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)