백준 3190 : 뱀 (삼성 SW 역량 테스트) _ C++

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

3190번: 뱀

 

#시뮬레이션 #큐 #gold4

 

회고

 

원래는 다른 분 코드를 많이 확인 한 문제는 업로드 하려 하지 않았으나, 참고하면서 문제 해결 능력이 많이 향상된 것을 느끼게 되어 해당 경험도 작성하려고 한다.

 

✔ 방향 전환

처음엔 방향 전환 하는 방법을 아예 접근조차 하지 못했어서 다른 분들 코드를 참고하면서 이해하려고 머리를 쥐어싸맸다.그런 노력 끝에 d라는 방향 설정을 통해 dx, dy 배열의 인덱스를 옮겨 다니면서 왼쪽, 오른쪽으로 방향 전환이 진행됨을 알 수 있었다.

슬프게도.. 이해는 했지만 방향 전환때문에 몇시간을 날린걸 생각하면..ㅎ.. 너무 슬프지만 덕분에 방향 전환에 대해 깊은 이해를 가질 수 있던 시간이었다고 생각한다. 해당 문제점은 뒤에..

 

✔ 큐

처음엔 뱀의 머리와 꼬리를 각각 두개의 큐로 나눠 저장해줬었는데, 너무 헷갈리기도 하고 그래서 그냥 큐를 한개로 저장해줬다.

다른 분 코드를 참고해보니 꼬리 위치가 중요한거였기때문에,

1) 사과가 있으면 머리 위치만 map 배열에서 몸통(1)으로 

2) 사과가 없을 경우 머리 위치는 몸통(1)으로, 원래 있던 꼬리 위치는 다시 0으로 초기화 해줘서 삭제해줬다. (그리고 큐에서 삭제.. //큐의 가장 첫번째 원소는 꼬리 위치다!!)

 

✔ 몇시간을 헤매다..

문제를 어제 접해서 오늘까지 약 7시간정도를 풀었는데 두번의 어려움이 있었다.

첫번째는 2번 테스트 케이스와 3번 테스트 케이스에서부터 정답을 출력하지 못한것이었고,

두번째는 주어진 테케는 통과했으나 '틀렸습니다' 가 뜨길래 반례를 찾아 돌려봤더니 많은 오답이 발견되었던 것 이었다.

 

첫번째 원인은 'X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전' 이 부분에서 끝난 뒤에를 제대로 적용시키지 못해 발생했던 것이었고

 

두번째는 .. 방향 전환 연산을 잘못 해줬던 것이었다..

if (cc == 'D') 	d = (d + 1) % 4;
else d = (d - 1) % 4;

-1 % 4 가 문제였던건데..  파이썬에서는 3으로 잘 나오는데 이 부분은 c++과 파이썬의 연산 차이였고 그 부분을 헷갈려했던 나머지 해당 문제점을 파악하지 못하고 몇시간을 헤맸다.. 참고로 c++에서는 -1이 나온다.

따라서 해당 연산을 -1 을 +3 으로 변경해줬고 그 결과 '정답입니다' 를 띄울 수 있었다.

 

코드

 

https://excited-hyun.tistory.com/217

[백준 3190 - C++] 뱀

 

이 분 덕분에 문제 이해를 더 잘 할 수 있었고, 잘 해결할 수 있었다. (코드가 굉장히 유사해서 업로드 하지 않을 생각이었지만 해당 문제를 통해 깨달은게 많았기 때문에 기록용으로 업로드 했다)

 

#include <iostream>
#include <queue>
#define MAX 110
using namespace std;

int n, k, l, x;
char cc;
int d = 0;
queue<pair<int, int>> q;
int map[MAX][MAX];
//동남서북
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };


int main() {
	cin >> n >> k;
	int r, c;
	for (int i = 0; i < k; i++) {
		cin >> r >> c;
		map[r][c] = 2; //사과
	}
	cin >> l;
	int time_cnt = 0;
	q.push({ 1,1 });
	int nx = 1;
	int ny = 1;

	for (int i = 0; i < l; i++) {
		cin >> x >> cc;
		while (time_cnt < x) {
			nx += dx[d];
			ny += dy[d];
			time_cnt++;

			if (nx <= 0 || nx > n || ny <= 0 || ny > n) {
				cout << time_cnt;
				return 0;
			}
			q.push({ nx,ny }); //꼬리위치

			if (map[nx][ny] == 1) {//몸통
				cout << time_cnt;
				return 0;
			}

			if (map[nx][ny] == 2) {//사과
				map[nx][ny] = 1;
				continue;
			}
			else {
				map[nx][ny] = 1; //머리
				int tx = q.front().first;
				int ty = q.front().second;
				map[tx][ty] = 0; //꼬리 위치 삭제
				q.pop();
			}
		}

		if (cc == 'D') {
			d = (d + 1) % 4;
		}
		else {
			d = (d + 3) % 4;
		}
	}

	while (1) {
		nx += dx[d];
		ny += dy[d];
		time_cnt++;

		if (nx <= 0 || nx > n || ny <= 0 || ny > n) {
			cout << time_cnt;
			return 0;
		}
		q.push({ nx,ny }); //꼬리위치

		if (map[nx][ny] == 1) {//몸통
			cout << time_cnt;
			return 0;
		}

		if (map[nx][ny] == 2) {//사과
			map[nx][ny] = 1;
			continue;
		}
		else {
			map[nx][ny] = 1; //머리
			int tx = q.front().first;
			int ty = q.front().second;
			map[tx][ty] = 0; //꼬리 위치 삭제
			q.pop();
		}
	}
	return 0;
}