백준- 8911 거북이

www.acmicpc.net/problem/8911

8911번: 거북이

---

문제

거북이가 이동한 영역을 포함하는 가장 작은 직사각형의 넓이를 구해라

---

풀이

거북이의 행 좌표값의 최대,최솟값. 열 좌표값의 최대,최솟값을 커맨드 실행 시마다 업데이트 후 

결과값 = 최대행값-최소행값 * 최대열값-최소열값

으로 넓이를 구하였다.

---

주의

거북이의 시작 좌표가0,0이기 때문에 최대,최소값을 Integer.MAXVALUE, Integer.MINVALUE로 잡을 시 -1이 최대 열값이 나올수 있다. 따라서 평소와 다르게 max,min의 값을 모두 0으로 초기화 시켜주었다.

---

package study.week7;

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

public class Main {
	static int dr[]	= {-1,0,1,0};
	static int dc[]	= {0,1,0,-1};
	static int maxr,maxc,minr,minc,r,c;
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/거북이.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			String cmd = sc.next();
			char cmds[] = cmd.toCharArray();//글자 몇개가 들어올지 모르므로
			int d = 0; //처음에 거북이가 북쪽을 쳐다보고있음.
			r=0;c=0;
			//Integer.MIN,MAX value로 하면 안된다. 0,0이 시작점이기 때문.
			maxr=0; maxc=0;
			minr=0; minc=0;
			
			for (int i = 0; i < cmds.length; i++) {
				char command = cmds[i];
				switch (command) {
				case 'F':
					r += dr[d];
					c += dc[d];
					update();
					break;
				case 'B':
					r -= dr[d];
					c -= dc[d];
					update();
					break;
				case 'L':
					//왼쪽으로 방향 변경
					d = (d - 1 + 4)%4;
					break;
				case 'R':
					//오른쪽으로 방향 변경
					d = (d + 1 + 4)%4;
					break;
				}
			}//end command
			//System.out.println(maxr +" "+maxc +" "+minr+" "+minc);
			int res = Math.abs(maxr - minr) * Math.abs(maxc - minc);
			System.out.println(res);
		}
	}
	static void update() {
		maxr = Math.max(maxr, r);
		maxc = Math.max(maxc, c);
		minr = Math.min(minr, r);
		minc = Math.min(minc, c);		
	}

}

---

모듈러 연산

0 1 2 3 의 인덱스를 가진 배열이 있다고 가정해보자. 이 배열을 뱅글뱅글 돌면서 참조하는 방법

 

인덱스를 오른쪽 방향으로 1씩 증가시킨다고 가정해보자.

0->1, 1->2, 2->3, 3->4가 될 것이다.

마지막인덱스는 배열의 인덱스 범위를 벗어나게 된다.

이때 모듈러 연산을 사용해주면 ( 3 + 1 + 4 ) % 4 = 0 , 첫번재 인덱스를 얻을수 있다.

---

공식

( 현재 인덱스 + 더해줄 값 + 배열의 크기 ) % 배열의 크기

---