백준 15949 Piet

https://www.acmicpc.net/problem/15949

프로그래밍 언어 중 하나인 Piet의 작동 원리를 구현하는 문제입니다.

먼저 전처리 과정을 거칩니다. 일단 dfs를 사용하여 블록을 탐색하고 각 블록에 번호를 부여합니다. 이후 각 블록에 대해 모든 dp와 cc 값으로 결정되는 코델의 좌표를 찾아 저장합니다. 코델의 좌표는 n과 m이 100 이하이므로 m*i+j의 정수형태로 저장하였습니다. 저장문제에 나와있듯 cc가 dp 방향에 상대적임에 유의하고 프로그램을 작성합니다.

작동의 구현은 다음과 같습니다. cnt가 0일 때 현재 코델의 문자를 출력한 후 현재 상태를 업데이트하고, 0이 아닐 때 cnt에 맞게 dp와 cc를 조정합니다. 이후 여러 변수들이 가리키는 코델의 좌표를 구해 범위를 벗어나거나 검정색(‘X’ 문자)을 가리키는지 확인하고 cnt 값을 조정하도록 구현하면 완성입니다.

#include<bits/stdc++.h>
using namespace std;
int n,m;
char cod[105][105]; // 코델의 색깔을 저장하는 배열
int blk[105][105]; // 각 코델이 몇 번째 블록에 속해있는지 저장하는 배열
int tgt[10005][4][2]; // 각각의 블록에 대해 dp와 cc에 의해 정해지는 코델의 좌표를 저장하는 배열
int di[4]={-1,0,1,0};
int dj[4]={0,1,0,-1};

void dfs(int i,int j,int idx) {
	blk[i][j]=idx;
	for(int k=0;k<4;k++) {
		int ii=i+di[k];
		int jj=j+dj[k];
		if(ii<0||ii>=n||jj<0||jj>=m) continue;
		if(cod[i][j]!=cod[ii][jj]) continue;
		if(blk[ii][jj]!=-1) continue;
		dfs(ii,jj,idx);
	}
}
void check(int i,int j,int k,int lr) {
	if(tgt[blk[i][j]][k][lr]==-1) tgt[blk[i][j]][k][lr]=m*i+j;
}
int main() {
	memset(blk,-1,sizeof(blk));
	memset(tgt,-1,sizeof(tgt));
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf(" %c",&cod[i][j]);

  // dfs 탐색
	int idx=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(blk[i][j]==-1) dfs(i,j,idx++);

  // dp와 cc로 결정되는 코델 좌표 저장
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) check(i,j,0,0);
		for(int j=m-1;j>=0;j--) check(i,j,0,1);
	}
	for(int j=m-1;j>=0;j--) {
		for(int i=0;i<n;i++) check(i,j,1,0);
		for(int i=n-1;i>=0;i--) check(i,j,1,1);
	}
	for(int i=n-1;i>=0;i--) {
		for(int j=m-1;j>=0;j--) check(i,j,2,0);
		for(int j=0;j<m;j++) check(i,j,2,1);
	}
	for(int j=0;j<m;j++) {
		for(int i=n-1;i>=0;i--) check(i,j,3,0);
		for(int i=0;i<n;i++) check(i,j,3,1);
	}

  // 동작 구현
	int cnt=0;
	int cur=blk[0][0];
	int dp=1,cc=0,ii=0,jj=0; // dp의 초기값이 1인 것은 di와 dj로 나타낸 방향벡터 중 두 번째가 오른쪽을 나타내기 때문이다.
	while(cnt<8) {
		if(cnt==0) {
			printf("%c",cod[ii][jj]);
			cur=blk[ii][jj];
		}
		else {
			if(cnt%2) cc=(cc+1)%2;
			else dp=(dp+1)%4;
		}
		ii=tgt[cur][dp][cc]/m+di[dp];
		jj=tgt[cur][dp][cc]%m+dj[dp];
		if(ii<0||ii>=n||jj<0||jj>=m) cnt++;
		else if(cod[ii][jj]=='X') cnt++;
		else cnt=0;
	}

	return 0;
}