백준 1491번 [나선](C++) -yes6686- 티스토리

백준 1491번: 나선

---

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

문제 설명:

주어진 \( n \times m \) 크기의 격자에서 나선형으로 이동하며 격자를 채우는 과정에서 최종적으로 도달한 좌표를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int visited[5001][5001]; // 방문 여부를 저장하는 배열

int main() {
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    visited[m - 1][0] = 1; // 시작 지점 설정
    int x = m - 1; // 현재 x좌표
    int y = 0;     // 현재 y좌표
    int d = 1;     // 방향 (1: 오른쪽, 2: 위, 3: 왼쪽, 4: 아래)
    int s = 2;     // 나선형에서 채운 칸의 개수
    int a = 0, b = 0; // x, y 변화량 합산

    while (true) {
        if (s > n * m) { // 모든 칸을 다 채운 경우
            cout << a << ' ' << b << '\n';
            break;
        }
        if (d > 4) d = 1; // 방향 초기화

        if (d == 1) { // 오른쪽 이동
            if (y + 1 >= n || visited[x][y + 1]) {
                d++; // 벽이거나 이미 방문한 경우 방향 변경
            } else {
                visited[x][y + 1] = 1; // 방문 표시
                s++;
                a++;
                y++;
            }
        } else if (d == 2) { // 위쪽 이동
            if (x - 1 < 0 || visited[x - 1][y]) {
                d++;
            } else {
                visited[x - 1][y] = 1;
                s++;
                b++;
                x--;
            }
        } else if (d == 3) { // 왼쪽 이동
            if (y - 1 < 0 || visited[x][y - 1]) {
                d++;
            } else {
                visited[x][y - 1] = 1;
                s++;
                a--;
                y--;
            }
        } else { // 아래쪽 이동
            if (x + 1 >= m || visited[x + 1][y]) {
                d++;
            } else {
                visited[x + 1][y] = 1;
                s++;
                b--;
                x++;
            }
        }
    }
    return 0;
}

---

코드 설명

위 코드는 \( n \times m \) 격자를 나선형으로 이동하며 각 칸을 채우는 과정을 구현합니다. 주요 로직은 다음과 같습니다:

1. 입력 처리: 격자의 크기 \( n \)과 \( m \)을 입력받고, 시작 지점을 설정합니다.
2. 방향 설정: 방향은 순서대로 오른쪽, 위쪽, 왼쪽, 아래쪽 순으로 순환합니다.
3. 벽 및 방문 여부 확인: 이동하려는 칸이 격자의 경계를 벗어나거나 이미 방문한 경우 방향을 변경합니다.
4. 이동 및 누적 값 업데이트: 방문한 칸의 좌표 변화량을 \( a \)와 \( b \)에 합산합니다.

이 코드는 시뮬레이션 알고리즘을 사용하여 나선형 패턴을 효율적으로 탐색합니다.

---

결과

위 코드를 통해 문제를 해결할 수 있으며, 나선형으로 격자를 채우는 과정을 효과적으로 구현했습니다. 코드 최적화 및 개선 사항이 있다면 댓글로 공유 부탁드립니다!