백준 / 달팽이 / C++

*문제 출처는 백준에 있습니다.

문제 제목: 달팽이

문제 사이트: https://www.acmicpc.net/problem/1913

---

나의 풀이

(처음 풀이 -> 0,0 에서 시작)

#include <stdio.h>
#define MAX 1100

int N, FIND_NUM;
int fr, fc; // FIND NUM 좌표
int MAP[MAX][MAX] = { 0 };

void input() {
	scanf("%d", &N);
	scanf("%d", &FIND_NUM);
}

void printMAP() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			printf("%d ", MAP[r][c]);
		}
		putchar('\n');
	}
}

// 달팽이 이동 방향: 하 -> 우 -> 상 -> 좌
int dx[4] = {0,1,0,-1}; 
int dy[4] = {1,0,-1,0};

void makeSnail() {
	// 0,0 에서 시작해서 크기가 N과 같아지거나 MAP[r][c] 가 0이 아니라면 
	// MAP 에 숫자 입력
	// 만약 NUM == FIND_NUM 이면 
	// 좌표 저장
	int NUM = N * N;
	int r = 0;
	int c = 0;
	int index = 0;

	MAP[r][c] = NUM--;

	while (NUM > 0) {
		int nr, nc;
		if (MAP[r][c] == FIND_NUM) {
			fr = r + 1;
			fc = c + 1;
		}
		nr = r + dy[index];
		nc = c + dx[index];
		if ((0 <= nr && nr < N) && (0 <= nc && nc < N) && (MAP[nr][nc] == 0)) {
			r = nr;
			c = nc;
			MAP[r][c] = NUM--;
		}
		else{
			index = (index + 1) % 4;
			}
	}
	if (MAP[r][c] == FIND_NUM) {
		fr = r + 1;
		fc = c + 1;
	}
}

int main() {
	input();
	makeSnail();
	printMAP();
	printf("%d %d", fr, fc);
}

 

 

 

 

근데 여러 응용문제가 있기 때문에.. (예를 들어서 숨바꼭질이나 등등...)

 

안에서 시작하는 달팽이를 구현하는게 맞음

 

 

대충 이런 로직으로 가줍시다

 

안에서 밖으로

#include <stdio.h>
#define MAX 1100

int N, FIND_NUM;
int fr, fc; // FIND NUM 좌표
int MAP[MAX][MAX] = { 0 };

void input() {
	scanf("%d", &N);
	scanf("%d", &FIND_NUM);
}

void printMAP() {
	for (int r = 1; r < N + 1; r++) {
		for (int c = 1; c < N + 1; c++) {
			printf("%d ", MAP[r][c]);
		}
		putchar('\n');
	}
}

// 달팽이 이동 방향: 상 -> 우 -> 하 - > 죄
int dr[4] = { -1, 0 , 1, 0 };
int dc[4] = {0 ,1,0,-1}; 


void makeSnail() {
	int r, c, num, index;
	int nr, nc;
	r = c = ((N + 1) / 2);

	num = 1; // 배열에 적을 수
	index = 0; // 방향 인덱스

	int step = 0;
	
	MAP[r][c] = num++;

	// 2번씩 N 칸 이동 후 방향 바꿈
	for (int i = 0; i < (2 * N) - 1; i++) {
		if (i % 2 == 0) {
			step++;
		}
		for (int s = 0; s < step; s++) {
			if (MAP[r][c] == FIND_NUM) {
				fr = r;
				fc = c;
			}
			nr = r + dr[index];
			nc = c + dc[index];

			MAP[nr][nc] = num++;
			
			r = nr;
			c = nc;
		}
		index = (index + 1) % 4;
		

	}
		
		
}

int main() {
	input();
	makeSnail();
	printMAP();
	printf("%d %d", fr, fc);
}

 

참고로 이 풀이는 범위를 잘 지정해서 출력해야함 

void printMAP() {
	for (int r = 1; r < N + 1; r++) {
		for (int c = 1; c < N + 1; c++) {
			printf("%d ", MAP[r][c]);
		}
		putchar('\n');
	}
}

 

이렇게 출력하면 잘 나오지만..

 

 

범위를 수정해보면

void printMAP() {
	for (int r = 0; r <= N + 1; r++) {
		for (int c = 0; c <= N + 1; c++) {
			printf("%2d ", MAP[r][c]);
		}
		putchar('\n');
	}
}

 

요롷게 50 까지 뿅 하고 나타남

 

---

※ 알아야 할 것

- 안에서 밖으로 만드는 법도 많이 공부하자