BOJ 15949

21 Apr 2020 • ProblemSolving

Piet

문제출처

문제 해석

  • Piet으로 작성된 프로그램이 주어졌을 때, 프로그램이 종료할 때까지 거치는 블록의 색깔을 출력하는 문제입니다.
  • Piet 프로그램에서 단위 정사각형을 코델이라고 하며, 각 코델마다 특정 색깔이 칠해져 있습니다.
  • DP(Direction Pointer)와 CC(Codel Chooser)라는 두가지 값이 존재하고, DP는 상하좌우 중 하나이고 CC는 왼쪽 또는 오른쪽입니다.
  • 초기 각 방향은 DP: 오른쪽, CC: 왼쪽입니다.
  • 어떤 블록으로 이동할 지 선택하는 기준은 다음과 같습니다.
    1. 현재 블록의 코델들 중에서 DP방향으로 가장 멀리 위치한 코델을 찾습니다.
    2. 그 중 CC의 방향으로 가장 끝에 있는 코델을 선택합니다. CC의 방향은 상대적으로, DP 방향을 기준으로 하는 방향입니다.
    3. 위에서 선택한 코델에서 DP방향으로 맞닿은 코델이 포함된 블록이 다음 블록이 됩니다.
  • 픽셀 중, 검은색 블록 혹은 이미지의 경계를 넘어서는 구역이 존재하는 경우 다음과 같이 진행합니다.
    1. CC의 방향을 전환한 후 다시 이동을 시도합니다.
    2. CC의 방향을 전환한 후에도 이동이 안되면, CC의 값을 유지하고 DP를 시계방향으로 회전한 후 다시 시도합니다.
    3. 시계방향으로 회전한 후에도 이동이 불가할 경우, 1번으로 되돌아갑니다.
    4. 위 과정을 반복하여 총 8가지의 경우를 모두 시도했는데도 이동할 수 없는 경우, 종료합니다.

설계(25)

  • 솔직히, 지문을 읽으면서 단번에 이해하기 어려웠습니다. 그래서 예시를 한 단계씩 따라가면서 지문과 대조하여 이해하였습니다.
  • 결국에는, DP와 CC의 방향에 따른 최고 끝 좌표를 구하고 이동이 가능한지 체크하는 문제입니다.
  • 따라서, 단순히 하라는데로만 하면 되는 문제입니다.
  • dfs또는 bfs를 이용하여 모든 좌표를 탐색한 후, 각 DP에 따른 상대적 CC의 방향이 절대적으로 봤을 때 어느 방향인지 그려가면서 최고 끝점을 찾도록 구현하였습니다.

구현(20)

코드
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 101

int sx,sy,tx,ty;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
bool visited[MAXN][MAXN];
char map[MAXN][MAXN];
int N,M;
string ans;
int DP,CC;
bool finish,flag;
bool check_coord(int x, int y){
    // 오른쪽
    if (DP ==0){
        if (y == ty){
            // 왼쪽
            if (CC == 0) {
                return x < tx;
            }
            // 오른쪽
            else return x > tx;
        }
        return y > ty;
    }
    // 아래
    else if (DP ==1){
        if (x == tx){
            // 왼쪽
            if (CC == 0) {
                return y > ty;
            }
            // 오른쪽
            else return y < ty;
        }
        return x > tx;
    }
    // 왼쪽
    else if (DP ==2){
        if (y == ty){
            // 왼쪽
            if (CC == 0) {
                return x > tx;
            }
            // 오른쪽
            else return x < tx;
        }
        return y < ty;
    }
    // 위
    else{
        if (x == tx){
            // 왼쪽
            if (CC == 0) {
                return y < ty;
            }
            // 오른쪽
            else return y > ty;
        }
        return x < tx;
    }
}
void find_corner(int x, int y, char target){
    if (check_coord(x,y)) tx = x, ty = y;
    visited[x][y] = true;
    for (int k = 0; k< 4; k++){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx>=N || ny>=M) continue;
        if (visited[nx][ny] || map[nx][ny]!=target) continue;
        find_corner(nx,ny,target);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0 ; i<N; i++){
        cin >> map[i];
    }
    ans = map[0][0];
    while (1){
        int time = 0;
        flag = false;
        while (time<=8&&!flag){
            memset(visited,false,sizeof(visited));
            tx = sx;
            ty = sy;
            find_corner(sx,sy,map[sx][sy]);
            int nx = tx + dx[DP];
            int ny = ty + dy[DP];
            if (nx < 0 || ny < 0 || nx>=N || ny>= M || map[nx][ny]=='X'){
                if (time%2==0) CC = (CC+1)%2;
                else DP = (DP+1)%4;
            }
            else{
                sx = nx;
                sy = ny;
                ans += map[nx][ny];
                flag = true;
            }
            time++;
        }
        if (!flag) break;
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 0 ms

마무리

  • 지문을 이해하는데 시간이 오래걸린 구현문제였습니다.
  • 그 외에 구현자체는 어렵지 않았습니다. 왜 난이도가 solved.ac기준 플레티넘4인지 모르겠습니다.
  • 체감난이도는 골드 1이 적당한 거 같습니다.
 BOJ  UCPC2018

Related Posts