[백준 1913] 달팽이 (C#, C++) - soo:bak

문제 링크

1913번 - 달팽이

설명

홀수 N 크기의 격자를 달팽이 모양으로 숫자를 채우고, 주어진 목표 값의 좌표를 구하는 문제입니다. 중심에 1을 두고 바깥쪽으로 N 제곱까지 채웁니다.

접근법

먼저, 격자의 좌상단에서 시작하여 N 제곱부터 1까지 감소하며 숫자를 채웁니다. 방향은 아래, 오른쪽, 위, 왼쪽 순서로 회전합니다.

다음으로, 다음 칸이 범위를 벗어나거나 이미 채워져 있으면 방향을 시계방향으로 전환합니다. 채우는 과정에서 값이 목표 값과 같으면 해당 좌표를 저장합니다.

이후, 격자 전체를 출력하고 저장해둔 목표 값의 좌표를 출력합니다. 좌표는 1부터 시작합니다.

시간 복잡도는 O(N^2)입니다.

---

Code

C#

using System;
using System.IO;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var reader = new StreamReader(Console.OpenStandardInput());
      var writer = new StreamWriter(Console.OpenStandardOutput());

      var n = int.Parse(reader.ReadLine()!);
      var target = int.Parse(reader.ReadLine()!);

      var grid = new int[n, n];
      var dr = new int[] { 1, 0, -1, 0 };
      var dc = new int[] { 0, 1, 0, -1 };
      var dir = 0;
      var r = 0;
      var c = 0;
      var ansR = 0;
      var ansC = 0;

      for (var val = n * n; val >= 1; val--) {
        grid[r, c] = val;
        if (val == target) {
          ansR = r + 1;
          ansC = c + 1;
        }

        var nr = r + dr[dir];
        var nc = c + dc[dir];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr, nc] != 0) {
          dir = (dir + 1) % 4;
          nr = r + dr[dir];
          nc = c + dc[dir];
        }
        r = nr;
        c = nc;
      }

      for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
          writer.Write(grid[i, j]);
          if (j + 1 != n)
            writer.Write(" ");
        }
        writer.WriteLine();
      }
      writer.WriteLine($"{ansR} {ansC}");

      writer.Flush();
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

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

  int n, target;
  cin >> n >> target;

  vvi grid(n, vi(n, 0));
  int dr[4] = {1, 0, -1, 0};
  int dc[4] = {0, 1, 0, -1};
  int dir = 0, r = 0, c = 0;
  int ansR = 0, ansC = 0;

  for (int val = n * n; val >= 1; val--) {
    grid[r][c] = val;
    if (val == target) {
      ansR = r + 1;
      ansC = c + 1;
    }

    int nr = r + dr[dir];
    int nc = c + dc[dir];
    if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 0) {
      dir = (dir + 1) % 4;
      nr = r + dr[dir];
      nc = c + dc[dir];
    }
    r = nr;
    c = nc;
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++)
      cout << grid[i][j] << (j + 1 == n ? '\n' : ' ');
  }
  cout << ansR << " " << ansC << "\n";

  return 0;
}