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

문제 링크

1952번 - 달팽이2

설명

M×N 격자를 달팽이 모양으로 모두 채울 때, 이동이 막혀 방향을 틀어야 하는 횟수를 구하는 문제입니다. 시작은 왼쪽 위에서 오른쪽으로 진행합니다.

접근법

격자가 작으므로 직접 시뮬레이션합니다. 현재 위치와 진행 방향을 유지하면서, 다음 칸이 격자 밖이거나 이미 방문한 칸이라면 시계방향으로 회전하고 꺾은 횟수를 1 증가시킵니다. 이후 새 방향으로 이동합니다.

방문한 칸 수가 M×N이 될 때까지 반복하면, 방향을 바꾼 횟수가 정답입니다. 진행 방향 배열을 {오른쪽, 아래, 왼쪽, 위} 순으로 두면 회전은 인덱스를 하나씩 증가(mod 4)시키는 것과 같습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var m = int.Parse(parts[0]);
    var n = int.Parse(parts[1]);

    var dr = new int[] { 0, 1, 0, -1 };
    var dc = new int[] { 1, 0, -1, 0 };
    var visited = new bool[m, n];

    var r = 0;
    var c = 0;
    var d = 0;
    visited[r, c] = true;
    var cnt = 1;
    var turns = 0;

    while (cnt < m * n) {
      var nr = r + dr[d];
      var nc = c + dc[d];
      if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr, nc]) {
        d = (d + 1) % 4;
        turns++;
        nr = r + dr[d];
        nc = c + dc[d];
      }
      r = nr; c = nc;
      visited[r, c] = true;
      cnt++;
    }

    Console.WriteLine(turns);
  }
}

C++

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

typedef vector<bool> vb;
typedef vector<vb> vvb;

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

  int m, n; cin >> m >> n;
  int dr[4] = {0, 1, 0, -1};
  int dc[4] = {1, 0, -1, 0};
  vvb visited(m, vb(n, false));

  int r = 0, c = 0, d = 0;
  visited[r][c] = true;
  int cnt = 1, turns = 0;

  while (cnt < m * n) {
    int nr = r + dr[d];
    int nc = c + dc[d];
    if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
      d = (d + 1) % 4;
      ++turns;
      nr = r + dr[d];
      nc = c + dc[d];
    }
    r = nr; c = nc;
    visited[r][c] = true;
    ++cnt;
  }

  cout << turns << "\n";

  return 0;
}