[C++] 백준 1913번 - 달팽이 (구현)

문제 링크 : www.acmicpc.net/problem/1913

1913번: 달팽이

 

 

 

문제

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

9	2	3
8	1	4
7	6	5

25	10	11	12	13
24	9	2	3	14
23	8	1	4	15
22	7	6	5	16
21	20	19	18	17

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

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

 

 

 

---

 

 

접근 방법

1) N에 따른 회오리 수를 구해준다. (N/2번)

2) 각 회오리마다 시작 지점의 행과 열을 지정한다. (N/2 -1, N/2 -1)

3) 방향을 나타내는 배열 dr[4], dc[4]의 방향을 오, 아, 왼, 위  순서로 지정한다.

4) 시작 지점에서 전진을 하면서 숫자를 하나씩 증가시키며 이차원 배열을 채워 넣고, 일정 범위를 넘어가면 전진 방향을 바꾼다.

5) 이때 범위는 몇번째 회오리인지에 따라 달라지는데, 회오리가 i 번째라고 하면 행과 열의 범위는 N/2-i ~ N/2+i 가 된다.

 

회오리 하나의 칸을 다 채웠으면 다음 바깥쪽의 회오리를 채우며, 다음 회오리로 넘어갈 때 시작 지점을 행-1, 열-1 로 지정한다.

//
//  SM_BOJ1913_ 달팽이.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/01.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//


#include <iostream>
#include <utility>

using namespace std;

//오 아 왼 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

int map[1000][1000];
int main(){
    
    pair<int,int> p;
    
    int N, x;
    cin >> N >> x;
    
    int rotateCnt = N/2;        //회오리 수
        
    int num = 1;
    map[N/2][N/2] = num;
    
    int startR = N/2 -1;
    int startC = N/2 -1;
    for(int i = 1; i<=rotateCnt; i++){
        
        int r = startR;
        int c = startC;
        
        for(int d = 0; d<4;){
            int nr = r + dr[d];
            int nc = c + dc[d];
            
            if((N/2 -i<=nr && nr<=N/2+i) && (N/2 -i<=nc && nc<=N/2+i)){
                num+=1;
                map[nr][nc] = num;
                if(num==x){
                    p.first = nr + 1;
                    p.second = nc + 1;
                }
                r = nr; //다음 칸 전진
                c = nc;
            }
            else{   //범위 넘어갔으니 방향 바꿔야함
                d++;
            }
           
        }
          
        //시작점 바꾸기 -1, -1
        startR -= 1;
        startC -= 1;
        
    }
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cout << map[i][j] << " ";
        }cout << endl;
    }
    cout << p.first << " " << p.second ;
    
    
    
    return 0;
}