백준 1913. 막대기

백준 1913. 달팽이

이번엔 구현문제인줄 알았는데 시뮬레이션 문제였음

---

문제 분석

자연수 N이 주어지면, 1~N^2의 자연수를 달팽이 모양으로 N*N 배열에 채운다

이때 찾고자 하는 수가 주어지면, 이 수의 좌표를 출력하는 문제

입력

• 첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)
• 둘째줄에 위치를 찾고자 하는 수가 주어짐

출력

• N개 줄어 걸쳐 표를 출력
• N+1번째 줄에 해당 수의 좌표를 출력한다

예시 분석

1)

7
35

49 26 27 28 29 30 31
48 25 10 11 12 13 32
47 24 9 2 3 14 33
46 23 8 1 4 15 34
45 22 7 6 5 16 35
44 21 20 19 18 17 36
43 42 41 40 39 38 37
5 7

N = 7이면, 1~49까지 표에 채워야한다.

이후 35를 찾으면 (5,7)의 좌표에 위치하므로, 해당 표와 5 7을 출력한다

---

알고리즘

크게

1. 수학적인 식을 찾아 반복문을 통해 표를 채우는 방법

2. 실제로 시뮬레이션을 돌려서 표를 채우는 방법으로 나뉠것 같다

예를들어

(1,1) = N^2, (1,2) = (N-1)^2 + 1, (1,3) = (N-1)^2 + 2, … 이런식으로 수학적 규칙을 찾을수도 있겠지만

시뮬레이션을 통해 중심점으로부터 달팽이를 한마리 놓고, 직접 표를 채우도록 하는 방법도 있을것이다

공식을 찾다가 오히려 더 복잡해보이길레 시뮬레이션 방법 사용. 맵도 그렇게 크지 않으므로 4MB 내에서 처리 가능함

달팽이 한마리를 중앙점(N/2+1, N/2+1)에 놓고 달팽이 모양으로 회전시키면 다음과 같은 프로세스로 동작한다

1. 1을 놓고, 앞으로 한칸, 우회전
2. 2를 놓고, 앞으로 한칸, 우회전
3. 3을 놓고, 앞으로 한칸, 4를 놓고, 앞으로 한칸, 우회전
4. 5를 놓고, 앞으로 한칸, 6을 놓고, 앞으로 한칸, 우회전
5. 7을 놓고, 앞으로 한칸, 8을 놓고, 앞으로 한칸, 9를 놓고, 앞으로 직진 시도하나 실패

- 이후 표 전체를 출력하고, 표를 탐색해서 해당 수의 좌표를 출력

몇번 직진하고, 언제 우회전을 할 것인지를 정하는것이 시뮬레이션 구현 방법의 키 포인트다

1, 2는 1칸 3~4, 5~6은 2칸 7~9, 10~12 는 3칸 13~16, 17~20은 4칸 이런식으로 묶을 수 있을것이다

즉 같은 길이로 두 번 움직인 뒤, 움직이는 길이를 1 늘린다라는 규칙을 찾을 수 있음

1. 배열크기 N과, 찾을 수 입력받기
2. 초기 위치 세팅. (N/2+1, N/2+1)
3. 배열 밖으로 나갈때까지 반복하면서 맵을 채운다
	3-1. 현재 좌표에 숫자 기록
	3-2. 정해진 길이만큼 이동하면서 숫자 채우기
	3-3. 우회전
4. 맵을 다 채웠다면, 맵 전체를 출력 후, 해당 수의 좌표를 출력 후 종료

---

소스코드

#include <iostream>

using namespace std;

int N, M;
int map[1000][1000];
struct Snail {
	int y, x;
	int face = 0; // ↑→↓←순
	int max_len = 1; // 정해진 길이만큼 이동. 이 수는 2번 우회전할때마다 1씩 증가함
	int turn_right_cnt = 0;
	void TurnRight() {
		face = (face + 1) % 4 ;
	}
	bool TryMoveForward() {
		int dy = this->y, dx = this->x;
		if (face == 0) { dy--; }
		else if (face == 1) { dx++; }
		else if (face == 2) { dy++; }
		else if (face == 3) { dx--; }

		// 표 밖으로 벗어난 경우 실패
		if (dy < 1 || dx < 1 || dy > N || dx > N) return false;
		
		this->y = dy; this->x = dx;
		return true;
	}
} snail;

int main() {
	
	cin >> N >> M;

	snail.y = snail.x = N / 2 + 1;

	int cnt = 1;
	bool end_flag = false;
	while (1) {
		
		for (int i = 0; i < snail.max_len; i++) {
			map[snail.y][snail.x] = cnt++;
			if (!snail.TryMoveForward()) {
				end_flag = true;
				break;
			}
		}
		if (end_flag)
			break; 

		snail.TurnRight();
		snail.turn_right_cnt++;
		if (snail.turn_right_cnt == 2) {
			snail.turn_right_cnt = 0;
			snail.max_len++;
		}
		
	}

	int yy = -1, xx = -1;
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			cout << map[y][x] << " ";
			if (map[y][x] == M) {
				yy = y; xx = x;
			}
		}
		cout << '\n';
	}
	cout << yy << " " << xx;

	return 0;
}