BaekJoon 13901번: 로봇(C++)

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

13901번: 로봇

풀이법

1) 난이도가 어렵지 않은 시뮬레이션 문제였으나, 조건문을 짜는 과정에서 실수가 잦아서 여러 번에 끝에 정답에 도달할 수 있었다. (4%에서 계속 "틀렸습니다"가 나오시는 분들은 맨 밑의 TC를 확인하세요!)

2) bfs와 같은 재귀 과정을 사용하는 것이 더 효율적일 수 있으나 필자는 bfs 기반의 queue가 손에 익었기에 이를 활용해서 문제를 풀었다.

3) 방문한 칸을 표시하기 위해 visited 배열을 만들었으며, 장애물의 경우 arr배열에 1의 값을 넣었다. 

4) 가장 중요한 방향의 경우 dir vector에 담았으며, 상 하 좌 우 라는 값을 vx, vy라는 배열에 미리 넣어둠으로서 최대한 코드의 길이를 줄이려 노력하였다.

5) 총 4번의 방향 전환이 일어났을 때, 로봇이 갈 수 있는 곳이 없는 경우를 출력하기 위해 현재 방향 비교 + 3번의 다른 방향 비교를 진행하였다. index값보다 큰 값이 발생하여, 미리 지정된 배열의 크기에서 벗어나려 할때는 설정해 두었던 최소 index인 1로 index를 설정함으로서 네 방향 모두를 탐색할 수 있도록 하였다. 

6) Worst Case의 시간복잡도는 모든 공간에 로봇청소기가 돌 수 있으므로 O(mn)이 될 것이다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int r, c,k;
int sr, sc;
int arr[1001][1001];
bool visited[1001][1001];
int vx[5] = {0,-1,1,0,0};
int vy[5] = { 0,0,0,-1,1 };
vector<int> dir;
void move()
{
	visited[sr][sc] = true;
	queue<pair<int, pair<int,int>>> q;
	q.push({ sr,{sc,1 } }); //초기 방향은 dir[1]
	int lastX = sr;
	int lastY = sc;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int nowD = q.front().second.second; // dir의 index
		q.pop();
		lastX = nowX;
		lastY = nowY;

		int nextX = nowX + vx[dir[nowD]]; //기존 방향으로 진행
		int nextY = nowY + vy[dir[nowD]];
		if (nextX >= 0 && nextY >= 0 && nextX < r && nextY < c && arr[nextX][nextY] == 0 && !visited[nextX][nextY]) // 범위 안의 값이며
		{
			visited[nextX][nextY] = true;
			q.push({ nextX,{nextY,nowD} }); //dir의 index;

		}
		else // 기존 방향으로 진행이 불가능할때 
		{
			for (int i = 0; i < 3; i++)
			{
				if (nowD + 1 > 4)
					nowD = 1;
				else
					nowD++;

				int nextX = nowX + vx[dir[nowD]];
				int nextY = nowY + vy[dir[nowD]];


				if (nextX < 0 || nextY < 0 || nextX >= r || nextY >= c)
					continue;
				if (arr[nextX][nextY] == 0 && !visited[nextX][nextY])
				{
					visited[nextX][nextY] = true;
					q.push({ nextX,{nextY,nowD } });
					break;
				}
			}
			
		}
	}
	cout << lastX <<" "<< lastY<<"\n";

}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> r >> c >> k;
	for (int i = 0; i < k; i++)
	{
		int br, bc;
		cin >> br >> bc;
		arr[br][bc] = 1;// 벽 세우기
	}
	cin >> sr >> sc;//시작 위치
	dir.push_back(0);
	for (int i = 0; i < 4; i++)
	{
		int d;
		cin >> d;
		dir.push_back(d);
	}
	move();
}

 

히든 TC

3 3
2
1 0
1 2
2 2
1 2 3 4

 

ANS : 2 0