[백준] 3190 : 뱀 - JAVA

Troubleshooting

import java.util.*;
import java.io.*;

public class Main {
	
	public static class Location {
		int x;
		int y;
		public Location(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static class MoveInfo {
		int time;
		String direc;
		public MoveInfo(int time, String direc) {
			this.time = time;
			this.direc = direc;
		}
	}
	
	public static class Rotation {
		int x;
		int y;
		String direc;
		public Rotation(int x,int y, String direc) {
			this.x =x;
			this.y = y;
			this.direc = direc;
		}
	}
	
	static Location[] appleLocation;
	static Queue<MoveInfo> directLocation = new LinkedList<>();
	static Queue<Rotation> directTailInfo = new LinkedList<>();
	static Location head = new Location(0,0);
	static Location tail = new Location(0,0);
	static int[] dy = {0,1,0,-1};
	static int[] dx = {1,0,-1,0};
	static int headDirec, tailDirec, time = 0;
	static boolean isCrush, isBeApple = false;
	static boolean[][] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		visited = new boolean[N][N];
		visited[0][0] = true;
		int K = Integer.parseInt(br.readLine());
		appleLocation = new Location[K];
		for(int i=0; i<K; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			appleLocation[i] = new Location(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
		}
		int L = Integer.parseInt(br.readLine());
		
		for(int i=0; i<L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			directLocation.add(new MoveInfo(Integer.parseInt(st.nextToken()), st.nextToken()));
		}
		
		while(!isCrush) {
			time++;
			setHeadDirection();
			moveHead();
			checkCrush(N);
			if(isCrush) {
				System.out.println(time);
				break;
			}
			checkBeAppleForHead();
			if(!isBeApple) {
				setTailDirection();
				moveTail();
			}
		}		
	}
	
	public static void setHeadDirection() {
		if(directLocation.size() == 0) return;  // 예외 처리!!! 
		if(time == directLocation.peek().time+1) {
			String rotationInfo = directLocation.poll().direc;
			
			switch(rotationInfo) {
			case "L" :
				headDirec = (headDirec -1) <0 ? 4-(headDirec -1) : (headDirec -1);
				directTailInfo.add(new Rotation(head.x, head.y, "L"));
				break;
				
			case "D" :
				headDirec = (headDirec+1)%4;
				directTailInfo.add(new Rotation(head.x, head.y, "D"));
				break;
			}
		}
	}
	
	public static void moveHead() {
		head.x += dx[headDirec];
		head.y += dy[headDirec];
		
		
	}
	
	public static void checkCrush(int N) {
		// 선 
		if(head.x < 0 || head.x >= N || head.y <0 || head.y >=N) {
			isCrush = true;
			return;
		}
		// 후 
		if(visited[head.x][head.y]) {
			isCrush = true;
			return;
		}	
		visited[head.x][head.y] = true;
	}
	
	public static void checkBeAppleForHead() {
		for(int i=0; i<appleLocation.length; i++) {
			if(appleLocation[i].x == head.x && appleLocation[i].y == head.y) {
				isBeApple = true;
				return;
			}
		}
	}
	
	public static void setTailDirection() {
		if(directTailInfo.size() ==0) return; // 예외 처리!!! 
		if(directTailInfo.peek().x == tail.x && directTailInfo.peek().y == tail.y) {
			String rotationInfo = directTailInfo.poll().direc;
			
			switch(rotationInfo) {
			case "L" :
				tailDirec = (tailDirec -1) <0 ? 4-(tailDirec -1) : (tailDirec -1);
				break;
				
			case "D" :
				tailDirec = (tailDirec+1)%4;
				break;
			}
		}
	}
	
	public static void moveTail() {
		tail.x += dx[tailDirec];
		tail.y += dy[tailDirec];
		
		visited[tail.x][tail.y] = false;
	}

}

문제

테케 하나 돌려보고 맞았길래, 그냥 제출했는데 2,3번 테케에서 다른답이 나왔다.

원인

visited[head.x][head.y] = true; 에서 '행'이 y, '열'이 x이어야하는데, 그 반대로 적어뒀다.

해결

visited[head.y][head.x] = true;

이것말고도 자잘하게 몇개있었는데, 대부분은 다시 보니 잘 보였다.
행열작성하는 코드에서 내가 자주 y,x 순서를 헷갈린다 (습관대로 x,y 로 적는다..)
그래서 이 부분을 기억하고자 이 사항만 작성했다.

제출코드

import java.util.*;
import java.io.*;

public class Main {
	
	public static class Location {
		int x;
		int y;
		public Location(int y, int x) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static class MoveInfo {
		int time;
		String direc;
		public MoveInfo(int time, String direc) {
			this.time = time;
			this.direc = direc;
		}
	}
	
	public static class Rotation {
		int x;
		int y;
		String direc;
		public Rotation(int x,int y, String direc) {
			this.x =x;
			this.y = y;
			this.direc = direc;
		}
	}
	
	static Location[] appleLocation;
	static Queue<MoveInfo> directLocation = new LinkedList<>();
	static Queue<Rotation> directTailInfo = new LinkedList<>();
	static Location head = new Location(0,0);
	static Location tail = new Location(0,0);
	static int[] dy = {0,1,0,-1};
	static int[] dx = {1,0,-1,0};
	static int headDirec, tailDirec, time = 0;
	static boolean isCrush = false;
	static boolean[][] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		visited = new boolean[N][N];
		visited[0][0] = true;
		int K = Integer.parseInt(br.readLine());
		appleLocation = new Location[K];
		for(int i=0; i<K; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			appleLocation[i] = new Location(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
		}
		int L = Integer.parseInt(br.readLine());
		
		for(int i=0; i<L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			directLocation.add(new MoveInfo(Integer.parseInt(st.nextToken()), st.nextToken()));
		}
		
		while(!isCrush) {
			Boolean isBeApple = false;
			time++;
			setHeadDirection();
			moveHead();
			checkCrush(N);
			if(isCrush) {
				System.out.println(time);
				break;
			}
			isBeApple = checkBeAppleForHead();
			if(!isBeApple) {
				setTailDirection();
				moveTail();
			}
		}		
	}
	
	public static void setHeadDirection() {
		if(directLocation.size() == 0) return;  // 예외 처리!!! 
		if(time == directLocation.peek().time+1) {
			String rotationInfo = directLocation.poll().direc;
			
			switch(rotationInfo) {
			case "L" :
				headDirec = (headDirec -1) <0 ? 4+(headDirec -1) : (headDirec -1);
				directTailInfo.add(new Rotation(head.x, head.y, "L"));
				break;
				
			case "D" :
				headDirec = (headDirec+1)%4;
				directTailInfo.add(new Rotation(head.x, head.y, "D"));
				break;
			}
		}
	}
	
	public static void moveHead() {
		head.x += dx[headDirec];
		head.y += dy[headDirec];
	}
	
	public static void checkCrush(int N) {
		// 선 
		if(head.x < 0 || head.x >= N || head.y <0 || head.y >=N) {
			isCrush = true;
			return;
		}
		// 후 
		if(visited[head.y][head.x]) {
			isCrush = true;
			return;
		}	
		visited[head.y][head.x] = true;
	}
	
	public static boolean checkBeAppleForHead() {
		for(int i=0; i<appleLocation.length; i++) {
			if(appleLocation[i].x == head.x && appleLocation[i].y == head.y) {
				appleLocation[i].x = -1;
				appleLocation[i].y = -1;
				return true;
			}
		}
		return false;
	}
	
	public static void setTailDirection() {
		if(directTailInfo.size() ==0) return; // 예외 처리!!! 
		if(directTailInfo.peek().x == tail.x && directTailInfo.peek().y == tail.y) {
			String rotationInfo = directTailInfo.poll().direc;
			
			switch(rotationInfo) {
			case "L" :
				tailDirec = (tailDirec -1) <0 ? 4+(tailDirec -1) : (tailDirec -1);
				break;
				
			case "D" :
				tailDirec = (tailDirec+1)%4;
				break;
			}
		}
	}
	
	public static void moveTail() {
		visited[tail.y][tail.x] = false; //먼저 ! 
		tail.x += dx[tailDirec];
		tail.y += dy[tailDirec];
	}

}

주의할 것

이번 문제를 풀면서 자잘하게 실수한 게 꽤 많았다.
자잘한 것들은 반복해서 실수 할 가능성이 높기때문에 체화해야한다.
따라서 주의하고자하는것에 주석을 달아뒀다.

• 행,열 표현시 y,x 순서 헷갈리지 말자!
• 참조할 때 NPE가 날 수 있으므로 꼭 그 전에 예외처리를 해줘야한다!!!
• checkCrush함수에서 (visited[head.y][head.x])먼저 검사하면, 인덱스초과 에러가 발생한다. 따라서 (head.x < 0 || head.x >= N || head.y <0 || head.y >=N) 먼저 검사해야한다.
  -> 배열의 인덱스로 쓰는 경우 인덱스초과에 주의하자!!!!

공부할 코드

import java.util.*;
import java.io.*;

public class BOJ3190 {

	static int[][] map;
	static List<int[]> snake = new ArrayList<>();
	static int n, k, l;
	static HashMap<Integer, String> hash = new HashMap<>();
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 }; // 동 남 서 북

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());

		map = new int[n][n];
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			map[a][b] = 1;

		}

		l = Integer.parseInt(br.readLine());

		for (int i = 0; i < l; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			String c = st.nextToken();
			hash.put(x, c);
		}

		solve();

	}

	public static void solve() {
		int cx = 0, cy = 0;
		int time = 0;
		int d = 0;
		snake.add(new int[] { 0, 0 });

		while (true) {
			// 1. 시간재기
			time++;

			// 2. 뱀 이동하기
			int nx = cx + dx[d];
			int ny = cy + dy[d];

			// 3. 범위를 벗어나거나, 뱀 몸통 만날 때 종료
			if (isFinish(nx, ny))
				break;

			// 4. 사과가 있을 때 없을 때 처리
			if (map[nx][ny] == 1) {
				map[nx][ny] = 0;
				snake.add(new int[] { nx, ny });

			} else {
				snake.add(new int[] { nx, ny });
				snake.remove(0);
			}

			// 5. 방향을 바꿔주는 시간을 만날 때 방향 변경
			if (hash.containsKey(time)) {
				if (hash.get(time).equals("D")) {
					d += 1;
					if (d == 4)
						d = 0;
				} else {
					d -= 1;
					if (d == -1)
						d = 3;
				}
			}

			// 6. 현재값 업데이트
			cx = nx;
			cy = ny;
			// cx cy 업데이트 위에서
		}

		System.out.println(time);
	}

	public static boolean isFinish(int nx, int ny) {
		if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
			return true;
		}

		for (int i = 0; i < snake.size(); i++) {
			int[] t = snake.get(i);
			if (nx == t[0] && ny == t[1])
				return true;
		}
		return false;
	}

}

내 코드보다 깔끔한 것 같고, 자료구조도 더 적절한 것을 사용한 것 같아 공부한다.

• HashMap<Integer, String>으로 뱀의 방향변환 정보를 넣으면 좋다. hash.containsKey(time)으로 원하는 정보를 O(1)에 찾을 수 있기때문이다.
  -> 내가 작성한 코드는 정보를 큐에 넣어두고 사용하는 것인데, 시간이 정렬된 순으로 제공해줘서 다행이지 그렇지않았다면 내가 정렬해서 풀어야했으므로 시간이 더 들었을것이다.

• 뱀의 머리 위치를 리스트에 넣어서 저장하고, 꼬리는 맨 앞 원소를 지우는 형식으로 짤 수 있다.
  -> 뱀의 위치를 나는 visited 이차원배열에 표시했다. 충돌을 체크할 수 있어야하기때문이다.
  그런데 꼬리가 머리를 잘 따라오는것을 표현하려고 또 머리가 꺾는 방향과 위치를 저장할 큐가 필요했고 복잡해졌다..