백준 13460번 삼성기출 구술탈출2

 

문제의 알고리즘 자체는 어려운편은 아니지만, 예외 케이스가 많고 기저 사건이 다양하기 때문에 문제를 잘읽고

코드는 최대한, 실수가 나지 않게끔 길어지더라도, 명확하게 분류해서 잘짜는게 중요한듯 합니다.

 

알고리즘은 기본적인 BFS 최단 문제입니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;

int N, M;
string Map[10];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int oy, ox;
int bx, by;
int rx, ry;

struct pos {
	int bx, by;
	int rx, ry;
	int cnt;
	pos(int by, int bx,int ry,int rx, int cnt) :by(by), bx(bx), ry(ry), rx(rx),cnt(cnt) {}
};

bool visit[10][10][10][10];

int BFS() {
	queue<pos> q;
	q.push(pos(by, bx, ry, rx,0));

	while (!q.empty()) {
        // queue에서 pop
		int cpos[4] = {q.front().by, q.front().bx, q.front().ry, q.front().rx};
		int cnt = q.front().cnt; q.pop();
        
		if (cnt > 10) break; //횟수 제한 초과
        
		visit[cpos[0]][cpos[1]][cpos[2]][cpos[3]] = true;
        
        //정답
		if (cpos[2] == oy && cpos[3] == ox) return cnt;
		
        // 상 하 좌 우
		for (int i = 0; i < 4; i++) {
			int npos[4] = { cpos[0],cpos[1],cpos[2],cpos[3] }; //next pos
            
            // 0에 빠졌는지 flag
			bool flag = true;
			bool flag2 = true;
            
            //blue가 쭉 움직인다.		
			while (Map[npos[0]+dy[i]][npos[1]+dx[i]] != '#' && flag) {
				npos[0] += dy[i];
				npos[1] += dx[i];
				if (Map[npos[0]][npos[1]] == 'O') flag = false;
			}

		    
			//red가 쭉움직인다.
			while (Map[npos[2] + dy[i]][npos[3] + dx[i]] != '#' && flag2) {
				npos[2] += dy[i];
				npos[3] += dx[i];
				if (Map[npos[2]][npos[3]] == 'O') flag2 = false;
			}

			//블루가 구멍에 빠져버렸으면 이번 경우의 수는 스킵한다.
			if (!flag) continue;
		
			if (npos[0] == npos[2] && npos[1] == npos[3]) {
				// red blue 위치가 같은 경우
				// 원래 순서와 움직인 방향에 따라 red blue 순서를 재배치
				switch (i)
				{
				case 0:
					if (cpos[1] < cpos[3]) npos[3] -= dx[i];
					else npos[1] -= dx[i];
					break;
				case 1:
					if (cpos[1] < cpos[3]) npos[1] -= dx[i];
					else npos[3] -= dx[i];
					break;
				case 2:
					if (cpos[0] < cpos[2]) npos[2] -= dy[i];
					else npos[0] -= dy[i];
					break;
				case 3:
					if (cpos[0] < cpos[2]) npos[0] -= dy[i];
					else npos[2] -= dy[i];
					break;
				}
			}
			
			if (!visit[npos[0]][npos[1]][npos[2]][npos[3]]) {
				q.push(pos(npos[0], npos[1], npos[2], npos[3], cnt + 1));
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> Map[i];
	}
    
    //맵을 흝으며, B,R,O의 좌표를 저장
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			char tmp = Map[i][j];
			if (tmp == 'B') {
				by = i; bx = j;
			}
			if (tmp == 'R') {
				ry = i; rx = j;
			}
			if (tmp == 'O') {
				oy = i; ox = j;
			}
		}
	}

	cout << BFS();

}

이렇게 예외케이스가 많은경우, 

switch문을 사용하여 이쁘게 정리하는게 코드를 눈으로 볼 때 좋았던거 같습니다.

 

저는 쉽게 가려고 npos[4] , cpos[4] 등 배열을 그냥 썼는데,  변수의 의미가 제대로 보이지 않아 실수하기 쉬웠습니다.

이런 복잡한 케이스를 가지는 문제들은 Blue_xPos, Blue_yPos 등  정확한 변수이름을 써서 코딩하는 것이 실수를 줄일 수 있습니다.