문제
상근이는 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다.
- F: 한 눈금 앞으로
- B: 한 눈금 뒤로
- L: 왼쪽으로 90도 회전
- R: 오른쪽으로 90도 회전
L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 명령을 나열한 것을 거북이 로봇의 컨트롤 프로그램이라고 한다.
상근이는 자신의 컨트롤 프로그램으로 거북이가 이동한 영역을 계산해보려고 한다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 프로그램을 작성하시오. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다.
아래 그림에서 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 컨트롤 프로그램이 FLFRFLBRBLB인 경우에 거북이는 아래와 같이 움직인다. 회색으로 빗금친 부분이 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형이다. 넓이는 4가 된다.
거북이가 지나간 영역이 직사각형을 만들지 않는 경우도 있다. 예를 들어, FFLLFF인 경우에 거북이는 y축의 위로만 지나다닌다. 이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생각할 수 있다. 따라서, 선분의 경우에 넓이는 0이 된다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 있고, 길이는 500을 넘지 않는다.
출력
각 테스트 케이스에 대해서, 거북이가 이동한 영역을 모두 포함하는 가장 작은 직사각형의 넓이를 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class JUN8911 {
/* 거북이
F : 한 눈금 앞으로
B : 한 눈금 뒤로
L : 왼쪽으로 90도 회전(전진 X)
R : 오른쪽으로 90도 회전(전진 X)
다 이동한 후에 가장 왼쪽, 가장 오른쪽 차가 가로 길이
가장 상단, 가장 하단의 차가 세로 길이니까
그 둘을 곱한다
* */
static int[][] map;
static int top, bottom, left, right, d;
static int hight, width; // 가로 세로
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine()); // 거북이 조작 횟수
String[] commands = new String[N];
for(int i = 0; i < N; i++){
top = 0;
bottom = 0;
left = 0;
right = 0;
d = 0; // 0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽
hight = width = 0;
commands[i] = br.readLine();
tuttle(commands[i]);
sb.append(countArea()).append("\n");
}
System.out.println(sb);
}
// 거북이가 움직인다.
public static void tuttle(String c){
char[] command = c.toCharArray();
for(int i = 0; i < command.length; i++){
char temp = command[i];
if(temp == 'F' || temp == 'B'){
// 명령어가 F와 B 일때만 움직인다
move(command[i]);
} else if(temp == 'L' || temp == 'R'){
// 명령어가 L 과 R 일때는 방향만 바꿔준다.
changeD(command[i]);
}
}
}
// 직사각형 크기 구하기
public static int countArea(){
return (Math.abs(top-bottom)) * (Math.abs(left-right));
}
// 방향 바꿔주기
public static void changeD(char c){
if(c == 'L'){
d++;
} else{
d--;
}
// 0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽 범위 넘어가면 수정 해주기
if(d == 4){
d = 0;
} else if(d == -1){
d = 3;
}
}
public static void move(char c){
switch (d){
case 0: // 위 보고 있음
if(c == 'F'){
hight++;
top = Math.max(top, hight);
} else{
hight--;
bottom = Math.min(bottom, hight);
}
break;
case 1: // 왼쪽 보고 있음
if(c == 'F'){
width++;
left = Math.max(left, width);
} else{
width--;
right = Math.min(right, width);
}
break;
case 2: // 밑에 보고 있음
if(c == 'F'){
hight--;
bottom = Math.min(bottom, hight);
} else{
hight++;
top = Math.max(top, hight);
}
break;
case 3: // 오른쪽 보고 있음
if(c == 'F'){
width--;
right = Math.min(right, width);
} else{
width++;
left = Math.max(left, width);
}
break;
}
}
}
풀이
거북이 로봇은 명령을 받아 움직인다.
명령어는 F, B, L, R 이 있다.
그 움직임이 멈춘 후 그 범위를 포함하는
직사각형의 넓이를 구하는게 이 문제이다.
직사각형의 넓이를 구하는 공식은 다들 아시다시피
사각형의 넓이 = 너비 x 높이
그렇죠?
너비는 어떻게 구하죠?
가장 맨 왼쪽부터, 가장 맨 오른쪽까지의 거리겠죠?
높이는 어떻게 구하죠?
가장 위에서, 가장 아래까지의 거리겠죠?
그러면 우리에게 필요한건,
가장 위, 가장 아래, 가장 왼쪽, 가장 오른쪽의 값이 겠죠?
뭘 구해야 할지 알았으니 시작해봅시다.
1. 거북이 로봇을 명령에 따라 움직인다.
뭐 움직이게 하면 다 끝이긴 합니다.
움직임은 크게
1) 전진(F) 과 후진(B)
2) 방향 전환(왼 : L, 오 : R)
입니다.
1) 전진과 후진
public static void move(char c){
switch (d){
case 0: // 위 보고 있음
if(c == 'F'){
hight++;
top = Math.max(top, hight);
} else{
hight--;
bottom = Math.min(bottom, hight);
}
break;
case 1: // 왼쪽 보고 있음
if(c == 'F'){
width++;
left = Math.max(left, width);
} else{
width--;
right = Math.min(right, width);
}
break;
case 2: // 밑에 보고 있음
if(c == 'F'){
hight--;
bottom = Math.min(bottom, hight);
} else{
hight++;
top = Math.max(top, hight);
}
break;
case 3: // 오른쪽 보고 있음
if(c == 'F'){
width--;
right = Math.min(right, width);
} else{
width++;
left = Math.max(left, width);
}
break;
}
}
중복 처리가 안돼 있어서 조금 긴데
결국에 다 똑같은 겁니다.
가로 : hight, 세로 : width 라는 변수가 있습니다.
hight 의 최대값은 가장 위, 최저값은 가장 아래를 나타내고
width 의 최대값은 가장 왼쪽, 최저값은 가장 오른쪽을 나타내는 겁니다.
그렇기에
위( d == 0)를 보고 있을 때
F 면 hight 를 +1 해주고
B 면 hight를 -1 해줍니다.
아래 ( d == 2) 를 볼때는 이에 반대로 합니다.
왼쪽 ( d == 1)을 보고 있을 때
F 면 width 를 +1 해주고
B 면 width를 -1 해줍니다.
오른쪽 ( d == 3) 을 볼때는 이에 반대로 합니다.
2) 방향 전환
public static void changeD(char c){
// 0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽
if(c == 'L'){
d++;
} else{
d--;
}
if(d == 4){
d = 0;
} else if(d == -1){
d = 3;
}
}저는 int 형 변수 d의 값이
0 : 위, 1: 왼쪽, 2 : 밑, 3 : 오른쪽
이라고 사용하기로 했기에
위의 코드처럼 나왔습니다.
L 명령어에는 d--,
R 명령어에는 d++ 를
하면서 범위를(0 ~ 3) 넘어가면
맨 뒤(3), 맨 앞(0)으로 보내주는 거죠
2. 넓이를 구해준다.
public static int countArea(){
return (Math.abs(top-bottom)) * (Math.abs(left-right));
}
위에서 움직이면서 구한
가장 위, 아래, 왼, 오른쪽을 사용해서
넓이를 구하면 끝~ 입니다.
높이나 너비를 구하는 방식은 여러가지 있을 수 있기때문에
편한 방식으로 사용하시면 될 것 같아요.
봐주셔서 감사합니다 ㅎㅎ
'백준 > 실버' 카테고리의 다른 글
| 백준 > 9711번 > 피보나치 - JAVA (2) | 2023.06.02 |
|---|---|
| 백준 > 27535번 > 제주 초콜릿 지키기 - JAVA > CompareTo<T>로 List 정렬하기 (0) | 2023.04.01 |
| 백준 > 1992번 > 쿼드트리 - JAVA (0) | 2023.02.22 |
