[JAVA] 백준 3190 뱀

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	static int N, K, L;

	static class move implements Comparable<move> {
		int time;
		String des;

		public move(int time, String des) {
			super();
			this.time = time;
			this.des = des;
		}

		@Override
		public int compareTo(move o) {
			return this.time - o.time;
		}

	}

	static class point {
		int y, x;
		int dir;

		public point(int y, int x, int dir) {
			this.y = y;
			this.x = x;
			this.dir = dir;
		}
	}

	static int dy[] = { -1, 1, 0, 0 };
	static int dx[] = { 0, 0, 1, -1 }; // 상, 하, 우, 좌
	static move[] moves;
	static char[][] map;
	static ArrayList<point> baem;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		map = new char[N][N];

		K = Integer.parseInt(br.readLine());
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			map[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1] = 'A';
		}

		L = Integer.parseInt(br.readLine());
		PriorityQueue<move> s = new PriorityQueue<move>();
		for (int i = 0; i < L; i++) {
			st = new StringTokenizer(br.readLine());
			s.add(new move(Integer.parseInt(st.nextToken()), st.nextToken()));
		}

		int time = 0; // 시간 0초 세팅
		baem = new ArrayList<point>();
		baem.add(new point(0, 0, 2)); // 첫 뱀의 머리를 0, 0에 우측 방향으로 삽입
		while (true) {
			time++; //1초 경과

			int dir = baem.get(0).dir; // 뱀 머리의 방향을 가져온다.
			int heady = baem.get(0).y + dy[dir]; //방향으로 한칸 전진한다.
			int headx = baem.get(0).x + dx[dir];
			if (check(heady, headx))//해당 칸이 벽 또는 몸과 닿았는지 체크
				break;

			if (!s.isEmpty() && s.peek().time == time) { // move 배열의 가장 상단의 값과 시간이 일치하는지 체크
				dir = rotate(dir, s.poll().des); // 방향을 가져와 방향 변경
			}
			
			baem.add(0, new point(heady, headx, dir)); // 방향에 맞게 전진
			
			if (map[heady][headx] == 'A') { // 사과를 만나면
				map[heady][headx] = ' '; // 사과가 없어짐
				continue; // 꼬리를 제거하지 않고 다음 루프
			}
			baem.remove(baem.size() - 1); // 사과가 없었다면 뱀의 꼬리 제거
		}
		
		
		System.out.println(time);
	}

	private static boolean check(int heady, int headx) {
		if (heady < 0 || heady >= N || headx < 0 || headx >= N) //벽에 닿았을 경우
			return true;
		for (int i = 1; i < baem.size(); i++) { // 뱀의 몸통과 닿는지 체크
			if (heady == baem.get(i).y && headx == baem.get(i).x) {
				return true;
			}
		}
		return false;
	}

	public static int rotate(int dir, String dirc) { // 방향 전환
		// 0, 1, 2, 3
		// 상, 하,우,좌
		if (dirc.equals("L")) {
			if (dir == 0)
				dir = 3;
			else if (dir == 1)
				dir = 2;
			else if (dir == 2)
				dir = 0;
			else if (dir == 3)
				dir = 1;
		} else if (dirc.equals("D")) {
			if (dir == 0)
				dir = 2;
			else if (dir == 1)
				dir = 3;
			else if (dir == 2)
				dir = 1;
			else if (dir == 3)
				dir = 0;
		}
		return dir;
	}

}

 

특별한 알고리즘이 없는 구현 문제였다.

최근 몇 회사들의 코딩테스트를 보았는데, 알고리즘 위주보다는 구현유형의 문제들을 많이 만났다.

구현 문제를 풀 때는 문제를 자세히 이해한 후 기능 별 구현으로 문제를 풀어 나간다.

실제로 문제를 풀 때 기능별로 주석을 달아가며 풀어 나가는 습관을 들이고 있는데, 실수도 줄어들고 속도도 빨라지는 것이 체감된다.

 

모두 취뽀 화이튕!