[Baekjoon]3190.뱀

3190.뱀

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

3190번: 뱀

---

로봇청소기문제랑 비슷한 문제인것 같다. 재귀함수를 이용해서 풀어보려고 했지만 while문을 이용한 풀이가 더 직관적이고 이해하기 쉬워서 while문을 이용했다. 

 

문제에서는 좌상단이 (1,1)인데 나는 (0,0)으로 설정하고 풀기 위해 사과가 있는 위치를 입력받을때 행과 열에서 각각 1씩 뺀값을 r,c에 저장했다. 또한 몇 초가 지났을 때 어느 방향으로 꺾을지에 대한 정보를 저장할 time, dir 배열을 따로 생성해서 명령을 미리 모두 저장해둔다. 명령에서 D가 들어오면 1을 저장하고, L이 들어오면 0을 저장한다.

 

방향 배열을 생성할때 북, 동, 남, 서 순서대로 되도록 만들어서 %연산을 통해 방향을 그때 그때 바꿀 수 있도록 한다. 로봇청소기에서도 이와 같은 아이디어를 사용했다. 현재 방향 기준 상대적인 방향이 바뀔 때 이와 같은 방법을 사용하면 switch문이나 if문 대신 %연산을 통해 코드를 더 간결하게 짤 수 있다.

 

내 생각에 가장 핵심이 되는 부분은 꼬리의 위치를 갱신하는 것이다. 뱀의 머리가 사과가 없는 곳을 방문하면 꼬리의 위치를 뱀의 길이에 맞춰 이동시켜야 하는데 이것은 큐를 사용해서 풀면 간단히 해결된다. 뱀이 다음 위치에 방문할 때마다 다음 위치를 큐에 넣어주고 사과가 있다면 그대로 두고 없으면 Dequeue해서 꼬리 위치를 갱신한다.(큐의 헤드에는 항상 뱀의 꼬리 위치가 들어있음)

private static void start(int curX, int curY, int d) {

		snake = new LinkedList<>();
		snake.add(new Point(curX, curY));

		map[curY][curX] = 1;
		int curDir = d; // 현재 방향 
		int timeIdx = 0;

		while (true) {

			if (timeIdx < L && time[timeIdx] == sec) { // 시간이 되면 방향 전환
				if (dir[timeIdx] == 1) {
					curDir = (curDir + 1) % 4; // 오른쪽으로 90도 
				} else {
					curDir = (curDir + 3) % 4; // 왼쪽으로 90도 
				}
				timeIdx++;
			}

			int nextX = curX + dx[curDir];
			int nextY = curY + dy[curDir];

			if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) { // 벽이면 종료
				sec++;
				break;
			}
			if (map[nextY][nextX] == 1) { // 자기 몸에 부딪히면 종료
				sec++;
				break;
			}

			snake.add(new Point(nextX, nextY));
			if (map[nextY][nextX] == 2) { // 사과가 있으면
				map[nextY][nextX] = 1;
			} else {	// 없으면 
				map[nextY][nextX] = 1;
				
				Point p = snake.poll(); // 꼬리 이동 
				int tailX = p.x;
				int tailY = p.y;
				map[tailY][tailX] = 0;

			}
			curX = nextX;
			curY = nextY;
			sec++;
		}
	}

<전체코드>