[백준] 1913 달팽이 C++

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

 

해설

n은 홀수 이기때문에 시작행은 n / 2, 시작 열 : n / 2에서 부터 1을 넣고 방향을 변경해가며 그대로 배열에 값을 채워 넣으면 되는 문제이다.

즉 가운데부터 순서대로 값을 채우는 것이다.

본인은 시작행, 시작열을 기준으로 level이라는 개념을 두어 범위를 벗어나거나 시작행과 시작열로 부터 level을 벗어난 경우 방향을 변경해 가며 2차원 배열의 값을 채워 나갔다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>

using namespace std;
using ll = long long;
#define endl "\n"

const int MAX = 1000;
int arr[MAX][MAX];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n; cin >> n;
	int goal = 0; cin >> goal;
	int rr, rc;
	int now = 1;
	int dir = 0;
	int level = 1;
	int r = n / 2, c = n / 2;
	int sr = n / 2, sc = n / 2;
	arr[sr][sc] = now;
	if (goal == 1)
	{
		rr = sr;
		rc = sc;
	}
	while (now < n * n)
	{
		if (dir >= 4)
		{
			dir = 0;
			level++;
			continue;
		}

		int nr = r + dr[dir];
		int nc = c + dc[dir];

		// 다음으로 갈 행과 열이 범위를 벗어나거나 level을 벗어난 경우 방향을 변경한다.
		if (nr < 0 || nr >= n || nc < 0 || nc >= n || (nr > sr + level) || (nr < sr - level) || (nc > sc + level) || (nc < sc - level))
		{
			dir++;
			continue;
		}
		
		arr[nr][nc] = ++now;
		r = nr; c = nc;
		if (now == goal) { rr = r; rc = c; }
	}
	
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
			cout << arr[i][j] << " ";
		cout << endl;
	}
	cout << rr + 1 << " " << rc + 1 << endl;

	return 0;
}

 

후기

40분 정도 걸렸는데 nr, nc의 범위를 확인할때 level보다 작은 경우에 대해서도 체크를 해주어야 올바르게 동작한다.

n은 홀수라는 점과 문제 그대로 구현할 수 있는지가 중요했던 문제라고 생각한다.