Baekjoon 8911 거북이 JAVA

8911번: 거북이

문제

해당 문제는 거북이 로봇에게 명령을 하고 난 뒤 거북이 로봇의 이동 경로를 통해 이동 경로가 모두 포함되는 가장 작은 직사각형의 넓이를 구하는 문제다.

조건

명령어는 총 네 가지가 있으며, F : 직진, B : 후진, R : 우회전, L : 좌회전이다.

L과 R명령에 대해서는 이동이 아닌 회전만 진행한다.

시작은 북쪽을 보며 시작한다.

직사각형을 만들지 않는 경우도 존재한다.

풀이

해당 문제를 처음 보고 map를 갱신하면서 최종적으로 map를 탐색해서 y , x 값의 길이를 구해 포함되는 직사각형을 만들면 되겠다 생각했었는데 문제를 풀던중 그냥 좌표만 계속 갱신하면 되겠다고 생각이 들어 좌표값으로만 문제를 해결했다.

먼저 이동에 관해 상 우 하 좌 순으로 이동하도록 델타를 구성하였고, 시작 좌표와 각 좌표별 max, min값을 저장할 변수를 0으로 초기화하였다. 

turtle이라는 메서드를 이용해서 로직을 구현하였는데 F, B에 대해서는 직진과 후진이라 단지 델타 값을 더해주고 빼주는 식으로 하였고, R의 경우 dir(방향을 알려주는 index) 값을 1 증가시키고 만약 4가 넘을 경우를 위해 %4를 통해 0 1 2 3이 반복하도록 하였고, L의 경우 dir값을 1 감소시키고 삼항 연산자를 이용해서 0 1 2 3이 반복할 수 있도록 해주었고, 명령어를 하나씩 수행하고 나면 각 좌표별 max값과 min값을 갱신해주고 모든 명령어를 수행하고 나면 이동한 y좌표 길이와 x좌표 길이를 구해 둘을 곱해주면 가장 작은 직사각형의 넓이를 알 수 있다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static int dir, dy[] = { -1, 0, 1, 0 }, dx[] = { 0, 1, 0, -1 };
	static int y, x, maxy, maxx, miny, minx;
	static char[] msg;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			dir = x = y = maxy = maxx = miny= minx = 0;
			msg = br.readLine().toCharArray();
			turtle();
		}
	}

	static void turtle() {
		for (int i = 0; i < msg.length; i++) {
			if (msg[i] == 'F') { //직진 현재 방향값으로 +1칸 저장
				y += dy[dir];
				x += dx[dir];
			} else if (msg[i] == 'B') { //후진 현재 방향값으로 -1값 저장
				y -= dy[dir];
				x -= dx[dir];
			} else if (msg[i] == 'R') //우회전 dir+1 해주고 4가 되면 0이 되어야하므로 나머지 연산
				dir = ++dir % 4;
			else  // L
				dir = --dir < 0 ? 3 : dir; //좌회전 dir-1 해주고 삼항연산자를 이용해서 값 저장
			// 각각 좌표별 max, min값 갱신
			maxy = Math.max(y, maxy);
			maxx = Math.max(x, maxx);
			miny = Math.min(y, miny);
			minx = Math.min(x, minx);
		}
		// 작업 수행 끝나면 각 x,y별 길이를 더하고 곱해줌 => 결과값
		System.out.println((Math.abs(maxx)+Math.abs(minx)) * (Math.abs(maxy) + Math.abs(miny)));
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드