백준 1913번 [달팽이](C++) -yes6686- 티스토리

백준 문제 풀이: 1913 [달팽이]

---

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

문제 설명:

n×n 크기의 배열을 달팽이 모양으로 채우는 문제입니다. 숫자는 n×n부터 시작하여 1까지 채워지고, 찾고자 하는 수 k의 위치를 출력해야 합니다.

이동 방향은 다음과 같은 순서로 진행됩니다:

• 아래 → 오른쪽 → 위 → 왼쪽 순서로 반복

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1001][1001];

int dx[4] = { 1, 0, -1, 0 }; // 하, 우, 상, 좌
int dy[4] = { 0, 1, 0, -1 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    int x = 0, y = 0, d = 0; // 시작 위치 및 방향
    int targetX = 0, targetY = 0;

    for (int num = n * n; num > 0; num--) {
        arr[x][y] = num;
        if (num == k) {
            targetX = x + 1;
            targetY = y + 1;
        }

        int nx = x + dx[d];
        int ny = y + dy[d];

        if (nx < 0 || ny < 0 || nx >= n || ny >= n || arr[nx][ny] != 0) {
            d = (d + 1) % 4; // 방향 전환
            nx = x + dx[d];
            ny = y + dy[d];
        }

        x = nx;
        y = ny;
    }

    // 배열 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }

    // 찾고자 하는 수의 위치 출력
    cout << targetX << " " << targetY << '\n';

    return 0;
}

예제 입력:

5
11

예제 출력:

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
1 3

---

코드 설명

• 핵심 알고리즘: 달팽이 모양으로 배열을 채우면서 숫자를 감소시키고, 방향 전환을 수행합니다.
• 구현 세부사항:
  • 초기 방향은 아래(dx = 1, dy = 0)로 설정
  • 배열의 끝이거나 이미 채워진 칸을 만나면 방향을 변경
  • 입력받은 k의 위치를 저장하여 마지막에 출력
• 시간 복잡도: O(n²), 모든 칸을 한 번씩 방문하며 숫자를 채움

---

결과

입력된 크기 n에 따라 달팽이 모양으로 숫자를 채우고, 찾고자 하는 숫자의 위치를 정확히 출력합니다. 방향 전환 로직을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!