티스토리 뷰

문제 풀이

[BOJ 8911] 거북이

RiKang 2018.01.22 00:44

 2011 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8911 에서 채점할 수 있습니다.


풀이 )


1) 거북이가 거쳐간 모든 좌표들을 알 수 있다면,  직사각형의 크기는 (max_x-min_x) * (max_y-min_y) 로 구할 수 있습니다.

 (max_x = 거북이가 거쳐간 x 좌표중 최대값, min_x = 거북이가 거쳐간 x 좌표중 최소값, max_y, min_y 도 같은 식입니다.)


2) 이 문제와 같이 90도로 회전하면서 전진하는 상황은 아래의 배열을 선언하여 시뮬레이션할 수 있습니다.


1
2
3
// code by RiKang, weeklyps.com
int dx[4]={0-101}; // 위쪽, 왼쪽, 아럐쪽, 오른쪽으로 1칸 갈 때 x좌표의 변화입니다.
int dy[4]={10-10}; // 위쪽, 왼쪽, 아럐쪽, 오른쪽으로 1칸 갈 때 y좌표의 변화입니다.
cs


 이런 배열을 선언하고, (위쪽일 때 direction = 0, 왼쪽일 때 direction = 1, 아래쪽일 때 direction = 2, 오른쪽일 때 direction = 3)이 되는 변수 direction을 관리해주면, x+=dx[direction]; y+=dy[direction]; 을 통해 1칸 전진을 표현할 수 있습니다.


3)
 왼쪽으로 90도 회전, 오른쪽으로 90도 회전은 direction 을 변경해주면 가능합니다.


 왼쪽 회전 : direction = (direction+1)%4

 오른쪽 회전 : direction = (direction+3)%4


 direction = 0, 1, 2, 3 일 때를 각각 생각해보면 위와 같은 식으로 방향이 바뀜을 알 수 있습니다. 오른쪽 회전이 (direction-1)%4가 아닌 이유는 direction=0 일 경우에 문제가 되기 때문입니다.


2), 3)을 이용하여 거북이의 움직입을 따라가면서 min_x, max_x, min_y, max_y를 구해주면 해결할 수 있습니다.


 최종 코드 )


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// code by RiKang, weeklyps.com
// 2011 ACM-ICPC Daejeon regional - L
// BOJ 8911 거북이
 
#include <bits/stdc++.h>
using namespace::std;
 
char in[505];
int dx[4]={0-101}; // 위, 왼, 아, 오
int dy[4]={10-10};
 
void solve(){
    int x, y;
    int min_x, min_y, max_x, max_y;
    x=y=min_x=min_y=max_x=max_y=0;
    
    int direction = 0;
 
    scanf("%s",in);
    int n = strlen(in);
    for(int i=0; i<n; i++){
        if(in[i]=='F'){
            x+=dx[direction];
            y+=dy[direction];
        }
        else if(in[i]=='B'){
            x-=dx[direction];
            y-=dy[direction];
        }
        else if(in[i]=='L'){
            direction = (direction+1)%4;
        }
        else{
            direction = (direction+3)%4;
        }
        min_x = min(x, min_x);
        min_y = min(y, min_y);
        max_x = max(x, max_x);
        max_y = max(y, max_y);
    }
    printf("%d\n",(max_x-min_x)*(max_y-min_y));
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}
cs


'문제 풀이' 카테고리의 다른 글

스택 기본 문제 풀이  (4) 2018.01.22
[BOJ 8901] 화학 제품  (0) 2018.01.22
[BOJ 8911] 거북이  (0) 2018.01.22
[BOJ 8897] Slicing Tree  (0) 2018.01.11
[BOJ 8898] 스포츠 전문 채널 GSK  (0) 2018.01.11
[BOJ 8899] Square Annulus  (0) 2018.01.11