[BOJ] 백준 1952 달팽이2

출처: https://www.acmicpc.net/problem/1952

 Input 
5 3

 Output 

5

 

시계 방향으로 방향을 바꾸므로, → ↓ ← ↑ 순서로 방향을 바꿉니다.

벽에 부딪히거나 이미 그린(방문) 곳이면 방향을 전환하면 됩니다.

 

Q.달팽이 모양으로 표의 모든 지점을 완료한 시점은 언제일까?

A. 방향을 바꿨음에도 불구하고 더 이상 그릴 수 없는 곳인 경우입니다.

     즉, 방향을 바꾸고 진행할 곳이 이미 방문한 곳인 경우입니다.

---

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
 
bool visited[100][100];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
 
int main(void) {
    int M, N;
    cin >> M >> N;
 
    int x = 0, y = 0;
    int dir = 0;
    int answer = 0;
 
    // 모든 칸을 채울 때까지
    // 즉, 더이상 달팽이 모양을 그릴 수 없을 때까지
    while (1) {
        if (visited[x][y]) {
            cout << answer - 1 << endl;
            return 0;
        }
 
        visited[x][y] = true;
        int nextX = x + dx[dir];
        int nextY = y + dy[dir];
 
        if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N || visited[nextX][nextY]) {
            dir = (dir + 1) % 4;
            nextX = x + dx[dir];
            nextY = y + dy[dir];
            answer++;
        }
 
        x = nextX;
        y = nextY;
    }
}