[백준] 1913번 - 달팽이 (C언어) [Silver3]

input	output
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이 입력되면 중간 점을 기준으로 N*N 형태의 배열이 형성되고 배열은 달팽이 모양으로 숫자가 채워져야 한다. 배열을 중간부터 채우는것이 아니라 배열의 끝 부분부터 채우는 식으로 접근하였다. 

 

생각해 보아야 할 조건은 아래와 같다.

• 배열을 채울 방향을 설정한다.
  • 필자는 하 → 우 → 상 → 좌로 설정하였다. (방향 설정은 어떻게 풀이를 하냐느냐에 따라 다르다.)
• 배열을 채울 때 범위를 벗어난 경우 , 이미 채워진 경우에 방향을 전환한다.

 

전체 소스 코드는 아래와 같다.

#include <stdio.h>
#pragma warning(disable:4996)
/*
	9 2 3
	8 1 4
	7 6 5
*/
// 방향 : 하 -> 우 -> 상 -> 좌 
int d[4][2] = { {1,0}, {0, 1}, {-1, 0}, {0, -1} };
int snail[1000][1000];

int main() {
	int x, y;
	int a = 0, b = 0; // 하 우 상 좌 순으로 배열을 채울 변수
	int c = 0; 
	int p, q; // 위치 찾기에 사용될 변수
	scanf("%d", &x); // x : x*x 행렬
	scanf("%d", &y); // 행렬에서 어느 위치에 있는지 찾을 수

	for (int i = x * x; i > 0; i--) {
		snail[a][b] = i;
		if (i == y) { // 위치 찾기
			p = a + 1; 
			q = b + 1;
		}
		int dx = a + d[c][0]; 
		int dy = b + d[c][1];
		if (dx < 0 || dx >= x || dy < 0 || dy >= x || snail[dx][dy] != 0) { // 범위에서 벗어나거나 값이 들어간 경우 방향 전환
			c = (c + 1) % 4; // 방향 전환
		}
		a += d[c][0];
		b += d[c][1];
	}

	for (int i = 0; i < x; i++) {
		for (int j = 0; j < x; j++) {
			printf("%d ", snail[i][j]);
		}
		printf("\n");
	}

	printf("%d %d\n", p, q);


	return 0;
}

구현 자체는 로직이 간단하여 어렵지 않다. 배열을 어떻게 채우는지만 알게된다면 쉽게 풀 수 있는 문제이다.

 

실행결과

CASE1

[1913번]

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

1913번: 달팽이

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview