[C++] 소프티어 [인증평가(1차) 기출] 로봇이 지나간 경로

https://softeer.ai/practice/info.do?idx=1&eid=577&sw_prbl_sbms_sn=136100

Softeer

풀이

1. 경로 탐색이기 때문에 BFS로 문제를 해결했다. DFS로 풀어도 답은 동일하다.

2. Robot 구조체에는 현재 위치와, 방향을 담을 수 있는 변수(row, col, direction) 그리고 회전 후 전진을 판단하는 rotate 함수가 포함된다.

3. 출발 위치를 찾는 방법은, 현재 '#' 위치에서 4방향을 탐색한 후 '#'이 한개만 나온다면 그곳을 출발지점 및 방향으로 설정했다.

4. 커맨드를 담기위한 cmd 벡터를 선언했고, BFS 를 돌면서 방문한 지점은 0으로 바꿔준다(방문 체크 필요 없음).

5. 탐색 방향과 로봇의 현재 방향이 같다면 'A' 만 cmd에 push_back, 다르다면 rotate 함수를 사용해서 어느쪽으로 돌고 전진해야 하는지 반환 후 push_back한다.

6. 다음 위치와 방향을 업데이트 하고 큐에 push한다.

#include<iostream>
#include<vector>
#include<string>
#include <queue>
#include <string>

using namespace std;

int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int cnt, dir=0, curr_row, curr_col;

struct Robot{
	int row, col, direction;
	Robot(int a, int b, int c) {
		row = a;
		col = b;
		direction = c;
	}
	// 회전 비교
	string rotate(int d)
	{
		if (direction == 0) {
			if (d == 1) return "RA";
			else if (d==3) return "LA";
		}
		else if (direction == 1) {
			if (d==2) return "RA";
			else if (d==0) return "LA";
		}
		else if (direction == 2) {
			if (d==1) return "LA";
			else if (d==3) return "RA";
		}
		else if (direction == 3) {
			if (d==2) return "LA";
			else if (d==0) return "RA";
		}
	}
};

int main(int argc, char** argv)
{
	int H, W;
	string S;
	
	cin >> H >> W;
	vector<vector<int>> map(H+1, vector<int>(W+1, 0));
	vector<vector<int>> checked(H+1, vector<int>(W+1, 0));
	for (int i = 1; i <= H; i++) {
		cin >> S;
		for (int j = 0; j < W; j++) {
			if (S[j] == '#') {
				map[i][j+1] = 1;
			}
			else {
				map[i][j+1] = 0;
			}
		}
	}
	// 출발 위치, 방향 탐색
	for (int i=1; i<=H; i++){
		for (int j=1; j<=W; j++){
			cnt = 0;
			if (map[i][j] == 1){
				for (int k=0; k<4; k++){
					int nr = i + dr[k];
					int nc = j + dc[k];
					if(nr < 1 || nc < 1 || nr > H || nc > W) continue;
					if (map[nr][nc] == 1) {
						cnt++;
						dir = k;
					}
				}
				if (cnt == 1) {
					curr_row = i;
					curr_col = j;
					break;
				}
			}
		}
		if (cnt == 1) break;
	}
	// 시작위치, 방향 출력
	cout << curr_row << " " << curr_col << "\n";
	if (dir == 0) cout << ">" << "\n";
	else if (dir == 1) cout << "v" << "\n";
	else if (dir == 2) cout << "<" << "\n";
	else if (dir == 3) cout << "^" << "\n";
    
	//BFS
    vector<string> cmd;
    queue<Robot> q;
	q.push(Robot(curr_row, curr_col, dir));
	map[curr_row][curr_col]=0;
	
	while (!q.empty()) {
		Robot cp = q.front();
		q.pop();

		for (int i=0; i<4; i++){
			int nr = cp.row + dr[i];
			int nc = cp.col + dc[i];
			int nnr = cp.row + 2*dr[i];
			int nnc = cp.col + 2*dc[i];

			if(nr < 1 || nc < 1 || nr > H || nc > W) continue;
			if (map[nr][nc] == 1) {
            	//방문처리
				map[nr][nc] = 0;
				map[nnr][nnc] = 0;
                // 같은 방향이면 "A"만 추가하고 위치 업데이트
				if (cp.direction == i) { 
					cmd.push_back("A");
					cp.row = nnr;
					cp.col = nnc;
					q.push(cp);
				}
				else {
					// 현재 방향이랑 비교해서 cmd push, 위치 업데이트
					cmd.push_back(cp.rotate(i));
					cp.row = nnr;
					cp.col = nnc;
					cp.direction = i;
					q.push(cp);
				}
				
			}
		}
	}
	// 커멘드 출력
	for (auto i:cmd) {
		cout << i;
	}
	cout << "\n";
	
	return 0;
}