백준 1913 달팽이

작성일 | In |

Problem : 달팽이

유형 : 구현

문제 설명

첫째 줄에 홀수인 자연수 N이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.
N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다.
N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

예제 입력

1
2
7
35

예제 출력

1
2
3
4
5
6
7
8
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

해결 전략

달팽이 모양대로 잘.. 움직이면 된다.
만약 맵의 크기가 3x3인경우, 1~9까지의 수가 세팅된다.

첫번째 이동은 세로 아래로 3만큼
두번째 이동은 가로 우측으로 2만큼

세번째 이동은 세로 위로 2만큼
네번째 이동은 가로 좌측으로 1만큼

규칙이 보인다. 첫번째의 경우만 n만큼 이동하고 이후부터는 n-1만큼 이동을 2번 하면된다.
이때 증감을 두번 간격으로 번갈아가면서 움직이면된다.

주의할 점

  • 몇번을 움직이는지에 초점을 맞추면 문제가 쉬워진다.
  • 종료지점은 더 이상 움직이지 않을때이다.
  • 시작 위치 설정에 주의한다.

풀이

원하는 값을 찾았는지 확인하는 함수.

원하는 값을 찾은경우, 해당 좌표를 기억해 놓는다.

달팽이를 움직이는 함수

dir은 방향관련 변수이다.
현재 좌표에서 움직여야 하는 만큼 dir 방향으로 움직인다.

세로로 움직인 뒤에는 움직여야 하는 정도를 감소시킨다.
가로로 움직인 뒤에는 움직여야 하는 방향을 바꾼다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

int board[1001][1001];

int find_num, find_nx, find_ny;
int n, cnt;

void num_check(int nx, int ny) {
	if (cnt == find_num) {
		find_nx = nx;
		find_ny = ny;
	}
}

void output() {
	for (int i = 1; i <= n; ++i) {
		for (int ii = 1; ii <= n; ++ii) {
			cout << board[i][ii] << " ";
		}
		cout << "\n";
	}
	cout << find_nx << " " << find_ny << "\n";
}

void solve() {
	//3번씩 한번
	//2번씩 두번
	//1번씩 두번..
	int nx = 0, ny = 1;
	int dir = 1;
	int move_cnt = n;

	while (1) {
		for (int i = 0; i < move_cnt; ++i) {
			nx = nx + dir;
			num_check(nx, ny);
			board[nx][ny] = cnt--;
		}
		move_cnt--;
		if (move_cnt == 0)break;

		for (int i = 0; i < move_cnt; ++i) {
			ny = ny + dir;
			num_check(nx, ny);
			board[nx][ny] = cnt--;
		}
		dir = -dir;
	}
}

void input() {
	cin >> n >> find_num;
	cnt = n * n;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

	input();
	solve();
	output();

	return 0;
}

피드백

쉽게 풀 수 있는 방법이 없을까 생각해보자.
이 문제의 경우, 움직여야 하는 정도를 이용하면 쉽게 풀렸다.