구현 문제답게 시키는대로 잘하면 풀 수 있는 문제입니다. 시키는대로 잘하십쇼
15949번: Piet
Piet은 프로그래밍 언어의 하나로, 코드가 N×M의 2차원 이미지로 되어 있는 것이 특징이다. 이름의 유래는 추상화로 유명한 네덜란드의 화가인 피트 몬드리안(Piet Mondrian)이다. 다음의 이미지는 "He
www.acmicpc.net
문제 요약
Piet 프로그래밍 언어에 관한 문제입니다.
Piet 언어는 코드가 NxM 이미지로 이루어져있습니다. 이미지의 단위 정사각형을 코델(Codel)이라고 하며 각 코델마다 특정 색깔이 칠해져있습니다.
같은 색깔의 코델이 상하좌우로 연결된 블록이 프로그램의 최소 실행 단위가 됩니다. 맨 처음 실행되는 블록은 가장 왼쪽 위 코델이 포함된 블록이며, 규칙에 따라 다음에 실행될 블록으로 이동하는 과정을 반복합니다.
현재 블록에서 어떤 블록으로 이동할지를 결정하기 위한 DP(Direction Pointer)와 CC(Codel Chooser)라는 두 가지 값이 존재합니다.
- DP - 왼쪽, 오른쪽, 위쪽, 아래쪽 중 하나
- CC - 왼쪽, 오른쪽 중 하나
프로그램이 처음 실행될 때 DP의 값은 오른쪽, CC의 값은 왼쪽입니다.프로그램이 처음 실행될 때 DP의 값은 오른쪽, CC의 값은 왼쪽입니다.
어떤 블록으로 이동할지를 선택하는 기준
- 현재 블록의 코델들 중에서 DP의 방향으로 가장 멀리 위치한 코델을 찾는다. 블록이 볼록하지 않은 경우 이 코델들은 연속하지 않을 수 있다.
- 위에서 찾은 코델들 중 DP 방향을 향했을 때 CC의 방향으로 가장 끝에 있는 코델을 선택한다. 이 때 CC의 방향은 상대적인 방향임에 유의하라. 예를 들어, DP가 아래쪽을 가리키고 CC가 오른쪽을 가리키는 경우, 선택되는 코델은 가장 왼쪽에 있는 코델이 된다.
- 위에서 선택한 코델에서 DP의 방향으로 맞닿은 코델이 포함된 블록이 다음 블록이 된다.
하지만, 검은색 블록 혹은 이미지의 경계 바깥은 이동할 수 없는 구역입니다.
다음 블록이 검은색 블록이거나 이미지의 경계 바깥인 경우
- CC의 값이 왼쪽인 경우 오른쪽으로, 오른쪽인 경우 왼쪽으로 바꾼 후 다시 이동을 시도한다.
- CC의 값을 바꾼 후에도 이동할 수 없는 경우, CC의 값을 유지하며 DP를 시계방향으로 회전한 후 다시 이동을 시도한다.
- 시계방향으로 회전한 후에도 이동할 수 없는 경우, 1번으로 되돌아간다.
- 위 과정을 계속 반복하여 총 8가지의 경우를 모두 시도했는데도 이동할 수 있는 블록을 찾지 못한 경우, 프로그램이 종료된다.
Piet으로 작성된 프로그램이 주어졌을 때, 프로그램이 종료할 때까지 거치는 블록의 색깔을 출력하는 프로그램을 작성해야합니다.
풀이 요약
BFS와 정렬을 이용해 구현했습니다.
- BFS로 현 좌표가 포함된 블록의 영역을 구한다.
- 구해진 영역을 DP값을 기준으로 정렬하고, DP방향으로 부터 가장 멀리 위치한 곳 코델들을 구한다.
- DP방향으로 부터 가장 멀리 위치한 코델들을 CC값을 기준으로 정렬하고, CC방향으로 가장 멀리 위치한 코델을 구한다.
- 구한 코델에서 DP 방향으로 다음 칸으로 이동할 수 있으면 이동하고, 안되면 DP 및 CC를 바꾼다.
- 프로그램이 종료될 때까지 1 ~ 4 반복
정렬?
DP와 CC는 방향값이죠. 이 방향 값을 기준으로 코델들을 정렬합니다.
예를 들어, image[x][y] 이미지에, 방향 값이 오른쪽이면 BFS로 구해진 영역들을 y값 기준으로 내림차순 정렬합니다. 그럼 자연스럽게 오른쪽으로 멀리 떨어진 코델들부터 정렬이 되겠죠. 그럼 정렬된 벡터 제일 앞에 있는 코델녀석을 포함, 그 뒤에서부터 y좌표 값과 똑같은 코델들이 오른쪽으로 가장 멀리 위치한 코델들이 됩니다.
구현
전처리
Piet 이미지의 경계바깥을 X(검은색 블록)로 전처리 해줍니다.
선택사항입니다. 저는 다음 블록이 경계 바깥이거나 검은색 블록인지 검사할 때, 구현에 용이하고자 경계바깥을 X(검은색 블록)으로 전처리 하였습니다. 그럼 이동해도되는지 검사할 때 X값 인지만 검사해주면 되거든요. 물론 image는 최대 102 x 102 사이즈를 가져야합니다.
// 경계 부분을 X로 전처리
void preprocessing() {
for(int i = 0; i <= n + 1; i++)
image[i][0] = image[i][m + 1] = 'X';
for(int i = 0; i <= m + 1; i++)
image[0][i] = image[n + 1][i] = 'X';
}
해당 좌표의 블록 영역 찾기 (BFS)
간단하게 BFS로 해당 좌표의 영역을 구해줍니다.
// 해당 좌표의 블록 영역 찾기 (BFS)
vector<pair<int, int>> getBlock(pair<int, int> pos) {
vector<pair<int, int>> block;
queue<pair<int, int>> q;
bool visited[102][102];
const char color = image[pos.first][pos.second];
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
visited[i][j] = false;
visited[pos.first][pos.second] = true;
q.push(pos);
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
block.push_back({x, y});
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(visited[nx][ny] || image[nx][ny] != color) continue;
visited[nx][ny] = true;
q.push({nx, ny});
}
}
return block;
}
가장 멀리 떨어진 코델들 찾기 (정렬)
먼저 정렬 규칙을 정의합니다.
각 방향마다 정렬 규칙을 정의했습니다. pair<int, int> 클래스를 이용해 코델 좌표를 표현했습니다.
- 방향이 오른쪽이면, second 기준 내림차순 정렬
- 방향이 아래이면, first 기준 내림차순 정렬
- 방향이 왼쪽이면, second 기준 오름차순 정렬
- 방향이 위이면, first 기준 오름차순 정렬
bool compareRight(pair<int, int>& a, pair<int, int>& b) { return a.second > b.second; }
bool compareDown(pair<int, int>& a, pair<int, int>& b) { return a.first > b.first; }
bool compareLeft(pair<int, int>& a, pair<int, int>& b) { return a.second < b.second; }
bool compareUp(pair<int, int>& a, pair<int, int>& b) { return a.first < b.first; }
주어진 방향으로 가장 멀리 떨어진 코델을 반환하는 함수 만들기
DP 방향이든 CC 방향이든 주어진 방향을 기준으로, 주어진 block 영역(vector)를 정렬합니다. 그리고 첫 번째 녀석을 포함한 첫 번째와 똑같은 값을 가진 코델들을 반환합시다. 그럼 주어진 방향으로 가장 멀리 떨어진 코델들이 반환됩니다. (0 : 오른쪽, 1 : 아래, 2 : 왼쪽, 3 : 위)
// 방향에 따른 부분 블록 찾기 (정렬)
vector<pair<int, int>> getSubBlock(int direction, vector<pair<int, int>>& block) {
vector<pair<int, int>> subBlock;
switch(direction) {
case 0: sort(block.begin(), block.end(), compareRight); break; // 방향 오른쪽, y좌표 내림차순 정렬
case 1: sort(block.begin(), block.end(), compareDown); break; // 방향 아래, x좌표 내림차순 정렬
case 2: sort(block.begin(), block.end(), compareLeft); break; // 방향 왼쪽, y좌표 오름차순 정렬
case 3: sort(block.begin(), block.end(), compareUp); break; // 방향 위, x좌표 오름차순 정렬
}
int num;
if(direction == 0 || direction == 2){
num = block[0].second;
for(pair<int, int> pos : block) {
if(num == pos.second) subBlock.push_back(pos);
else break;
}
} else {
num = block[0].first;
for(pair<int, int> pos : block) {
if(num == pos.first) subBlock.push_back(pos);
else break;
}
}
return subBlock;
}
DP 방향으로 가장 멀리 떨어진 코델들 구하기
위에서 만든 함수에 DP값과, BFS로 구한 블록 영역을 전달합시다.
// dp 블록 찾기
vector<pair<int, int>> getDpBlock(int dp, vector<pair<int, int>>& block) {
return getSubBlock(dp, block);
}
CC 방향으로 가장 멀리 떨어진 코델 구하기
동일한 함수에 CC값과, DP 방향으로 가장 멀리 떨어진 코델들을 전달합시다.
DP 방향으로 가장 멀리 떨어진 코델들은 first나 second 필드들이 똑같은 값을 가지고, CC 방향은 무조건 DP방향의 +90도거나 -90도 방향을 가지게 때문에 자연스럽게 getSubBlock()에서 반환되는 벡터는 요소가 무조건 하나만 존재하는게 자명합니다.
// cc 코델 찾기
pair<int, int> getCcCodel(int cc, vector<pair<int, int>>& block) {
return getSubBlock(cc, block)[0];
}
전체적인 흐름
전처리 과정을 거치고, 본격적인 이동을 시작합니다.
현 좌표를 포함한 블록 영역 구하기 → 이 영역의 DP방향으로 멀리 떨어진 코델들 구하기 → DP방향으로 멀리 떨어진 코델들에서 CC방향으로 멀리 떨어진 코델 구하기
그리고 DP방향으로 한 칸 이동해 X인지 검사합니다. (전처리 과정을 거치지 않았다면 경계 바깥인지도 검사해야합니다.)
만약 X가 아니라면 다음 블록으로 이동하고, 맞으면 방향 전환하고 다시 시도하면 됩니다.
void solve() {
int failedCnt = 0, dp = 0, cc = 3;
char color = image[1][1];
pair<int, int> pos = {1, 1};
vector<char> path;
path.push_back(color);
preprocessing();
while(true) {
vector<pair<int, int>> block = getBlock(pos); // 해당 좌표의 색깔의 블록 영역을 찾는다.
vector<pair<int, int>> dpBlock = getDpBlock(dp, block); // 해당 블록의 dp 블록을 찾는다.
pair<int, int> ccCodel = getCcCodel(cc, dpBlock); // 해당 블록의 cc 코델을 찾는다.
pair<int, int> nextCodel = { ccCodel.first + dx[dp], ccCodel.second + dy[dp] }; // cc 좌표의 다음 좌표를 계산한다.
if(image[nextCodel.first][nextCodel.second] != 'X') { // 다음 좌표의 블록이 X 블록이 아니면
// 다음 블록으로 이동
color = image[nextCodel.first][nextCodel.second];
pos = { nextCodel.first, nextCodel.second };
path.push_back(color);
failedCnt = 0;
}
else { // 다음 좌표의 블록이 X 블록이면
// 방향 전환
failedCnt++;
if(failedCnt & 1) cc += 2;
else dp++, cc++;
dp %= 4;
cc %= 4;
}
if(failedCnt >= 8) break; // 8개 경우를 모두 실패했다면 프로그램을 종료한다.
}
for(char c : path) cout << c;
}코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n, m;
char image[102][102];
bool compareRight(pair<int, int>& a, pair<int, int>& b) { return a.second > b.second; }
bool compareDown(pair<int, int>& a, pair<int, int>& b) { return a.first > b.first; }
bool compareLeft(pair<int, int>& a, pair<int, int>& b) { return a.second < b.second; }
bool compareUp(pair<int, int>& a, pair<int, int>& b) { return a.first < b.first; }
// 경계 부분을 X로 전처리
void preprocessing() {
for(int i = 0; i <= n + 1; i++)
image[i][0] = image[i][m + 1] = 'X';
for(int i = 0; i <= m + 1; i++)
image[0][i] = image[n + 1][i] = 'X';
}
// 해당 좌표의 블록 영역 찾기 (BFS)
vector<pair<int, int>> getBlock(pair<int, int> pos) {
vector<pair<int, int>> block;
queue<pair<int, int>> q;
bool visited[102][102];
const char color = image[pos.first][pos.second];
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
visited[i][j] = false;
visited[pos.first][pos.second] = true;
q.push(pos);
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
block.push_back({x, y});
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(visited[nx][ny] || image[nx][ny] != color) continue;
visited[nx][ny] = true;
q.push({nx, ny});
}
}
return block;
}
// 방향에 따른 부분 블록 찾기 (정렬)
vector<pair<int, int>> getSubBlock(int direction, vector<pair<int, int>>& block) {
vector<pair<int, int>> subBlock;
switch(direction) {
case 0: sort(block.begin(), block.end(), compareRight); break; // 방향 오른쪽, y좌표 내림차순 정렬
case 1: sort(block.begin(), block.end(), compareDown); break; // 방향 아래, x좌표 내림차순 정렬
case 2: sort(block.begin(), block.end(), compareLeft); break; // 방향 왼쪽, y좌표 오름차순 정렬
case 3: sort(block.begin(), block.end(), compareUp); break; // 방향 위, x좌표 오름차순 정렬
}
int num;
if(direction == 0 || direction == 2){
num = block[0].second;
for(pair<int, int> pos : block) {
if(num == pos.second) subBlock.push_back(pos);
else break;
}
} else {
num = block[0].first;
for(pair<int, int> pos : block) {
if(num == pos.first) subBlock.push_back(pos);
else break;
}
}
return subBlock;
}
// dp 블록 찾기
vector<pair<int, int>> getDpBlock(int dp, vector<pair<int, int>>& block) {
return getSubBlock(dp, block);
}
// cc 코델 찾기
pair<int, int> getCcCodel(int cc, vector<pair<int, int>>& block) {
return getSubBlock(cc, block)[0];
}
void solve() {
int failedCnt = 0, dp = 0, cc = 3;
char color = image[1][1];
pair<int, int> pos = {1, 1};
vector<char> path;
path.push_back(color);
preprocessing();
while(true) {
vector<pair<int, int>> block = getBlock(pos); // 해당 좌표의 색깔의 블록 영역을 찾는다.
vector<pair<int, int>> dpBlock = getDpBlock(dp, block); // 해당 블록의 dp 블록을 찾는다.
pair<int, int> ccCodel = getCcCodel(cc, dpBlock); // 해당 블록의 cc 코델을 찾는다.
pair<int, int> nextCodel = { ccCodel.first + dx[dp], ccCodel.second + dy[dp] }; // cc 좌표의 다음 좌표를 계산한다.
if(image[nextCodel.first][nextCodel.second] != 'X') { // 다음 좌표의 블록이 X 블록이 아니면
// 다음 블록으로 이동
color = image[nextCodel.first][nextCodel.second];
pos = { nextCodel.first, nextCodel.second };
path.push_back(color);
failedCnt = 0;
}
else { // 다음 좌표의 블록이 X 블록이면
// 방향 전환
failedCnt++;
if(failedCnt & 1) cc += 2;
else dp++, cc++;
dp %= 4;
cc %= 4;
}
if(failedCnt >= 8) break; // 8개 경우를 모두 실패했다면 프로그램을 종료한다.
}
for(char c : path) cout << c;
}
void input() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> image[i][j];
}
int main(void) {
ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
input();
solve();
return 0;
}느낀점
아 구현문제 더 빡세게 해야겠다. 모듈화 잘해야겠다.
혹시 더 깔끔하고 아름답고 우아한 아이디어가 있으면 공유 부탁드립니다 ㅎㅎ
히힛 ><
