baekjoon 3190 : 뱀(snake)

오랜만에 알고리즘 문제 푸려니 너무 힘들었다.. 백준 기준 정답률 17%의 삼성 SW역량시험에 출제되었던 문제.

특정 class를 만들어 Queue를 이용하는 idea까진 생각해 냈지만, 문제에 대한 이해도가 부족했던 것 같다.

나에게 있어서 문제의 요지는 다음과 같았다.

 

1. 방향 설정을 간단하게 하기

처음에 east west 난리를 쳤다가 코드가 점점 길어졌다. L로 계속 돌면 반시계, D면 시계방향이라는 것을 뒤늦게 깨닫고 순환성을 이용하여 마침내 방향이 숫자가 될 수 있었다. 역시 수학을 잘 해야해.. 

2. queue에 무엇을 넣을 것인지? ★★★

머리와 꼬리만 알면 된다고 생각했는데 몸통도 알아야 한다. 그래서 뱀 전체를 queue에 넣었다. 꼬리는 queue의 head이므로 꼬리가 없어질 때마다 poll 해 주었다. 또한 몸통과 꼬리의 차이점은, 사과를 먹지 않았을 때에는 뱀의 길이가 변하지 않아 기존의 꼬리는 없어지기 때문에 머리와 꼬리가 닿아도 상관이 없지만 머리와 몸통이 닿았을 경우에는 종료되어야 한다는 점이다. 그래서 꼬리를 없앤 후 머리가 몸에 닿는지(꼬리가 이미 없어졌으므로 나머지는 몸이 된다) 검사하였다.

3. 결국 queue 말고 list 등 다른 자료구조를 이용하여 구현하여도 무관하다.

queue의 자료구조를 까먹었는지 head가 마지막 element인 줄 알고 현재 상태인 것으로 코딩했다. ^^.. 이 부분은 그냥 현재 상태를 저장하는 변수를 따로 만드니 간단히 해결되었다. head와 tail을 알 수 있는 자료구조이면 상관없을 것 같다.

4. 사실상 사과는 필요없다.

tail은 변하지 않고 head만 이동하기 때문. 이것은 0, 1, 2를 만났을 때 모두 공통적으로 적용되는 사항이다. 

 

  
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Index {
	int i, j;
	public Index(int a, int b) {
		this.i = a;
		this.j = b;
	}
}

public class Solution03 {
	
	static int time = 0;
	
	public static void main(String args[]) throws FileNotFoundException {
		//Scanner sc = new Scanner(System.in);
		Scanner sc = new Scanner(new FileInputStream("snake_problem_input.txt"));
		int size = sc.nextInt();
		int[][] map = new int[size+1][size+1];
		
		int appleNum = sc.nextInt();
		for (int i=0; i&ItappleNum; i++) {
			int ai = sc.nextInt();
			int aj = sc.nextInt();
			map[ai][aj] = 2;
		}
		int dirNum = sc.nextInt();
		int[] dirTime = new int[dirNum];
		char[] dirName = new char[dirNum];
		for (int i=0; i&It;dirNum; i++) {
			dirTime[i] = sc.nextInt();
			dirName[i] = sc.next().charAt(0);
		}
		
		// 0 east, 1 south, 2 west, 3 north
		// dir : L이면 +3, D이면 +1 (%4)
		int dir = 0;
		int[] dir_x = ;
		int[] dir_y = ;
		int k = 0;
		int curr_i = 1, curr_j = 1;
		Queue&It;Index> queue = new LinkedList&It;Index>();
		queue.add(new Index(curr_i,curr_j));
		map[curr_i][curr_j] = 1;
		
		while (!queue.isEmpty()) {
			
			Index head = new Index(curr_i, curr_j);
			int hi = head.i, hj = head.j;
			int ni = hi + dir_x[dir];
			int nj = hj + dir_y[dir];
			
			// 벽과 충돌이 일어날 경우, 1초 후에 충돌
			if (ni &It= 0 || nj &It= 0 || ni > size || nj > size) {
				time++;
				break;
			}
			
			// 사과를 먹지 않으면 꼬리 삭제
			if (map[ni][nj] == 0) {
				Index tail = queue.poll();
				map[tail.i][tail.j] = 0;
			}
			
			// 자기 자신을 만난 경우 1초 후에 충돌
			if (map[ni][nj] == 1) {
				time++;
				break;
			}
			
			// 머리 나아감
			queue.add(new Index(ni,nj));
			map[ni][nj] = 1;
			curr_i = ni; curr_j = nj;
			time++;
			
			// 방향 전환
			if (k &It; dirTime.length && dirTime[k] == time) {
				if (dirName[k]=='L') 
					dir = (dir+3)%4;
				else if (dirName[k]=='D')
					dir = (dir+1)%4;
				
				k++;
			}
			
		}
		
		System.out.println(time);
	}
}