백준 1491번 나선 C++

출처 : https://www.acmicpc.net/problem/1491

 

남서쪽이 (0, 0)이고 남동쪽이 (N-1, 0)이라고 했으니 ↓→↑← 순서로 돌아야 한다.

쭉 직진하다가 벽을 만나면 저 순서대로 도는 것을 반복하다가 만약 사방이 막혀있거나 이미 방문한 곳이라면 그곳이 나선이 끝나는 곳이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

int dRow[4] = { 1,0,-1,0 };
int dCol[4] = { 0,1,0,-1 };

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

	int n, m;
	cin >> n >> m;
	vector<vector<bool>> visited(n, vector<bool>(m, false));
	int row = 0;
	int col = 0;
	int dir = 0;
	visited[row][col] = true;
	int cnt = 0;
	while (true) {
		if (cnt >= 4) break;
		int nextRow = row + dRow[dir];
		int nextCol = col + dCol[dir];
		if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m || visited[nextRow][nextCol]) {
			cnt++;
			dir = (dir + 1) % 4;
			continue;
		}
		cnt = 0;
		row = nextRow;
		col = nextCol;
		visited[row][col] = true;
	}
	cout << row << " " << col;
};