[10157] 자리배정

https://www.acmicpc.net/problem/10157

10157번: 자리배정

<문제>

여러가지 구현 방법이 있겠지만, r*c가 100만뿐이 안되므로 모든 칸을 순회하도록 구현해도 괜찮다.

재귀를 이용해서 다음에 방문할 좌표에 대해서,

(좌표가 범위를 벗어나는 경우) || (이미 방문한 좌표) 일때에는 방향을 회전하고

그 외에는 정상적인 탐색범위이므로 방향을 회전하지 않고 그대로 진행한다.

이경우 O(R*C)의 시간복잡도가 나온다.

 

이문제는 위처럼 구현해도 TLE가 발생하지 않는 범위의 입력만 주어지나, 조금더 효율적인 방법을 고안해보면

입력받은 R*C의 직사각형을 하나의 행또는 열에 대해서 자르는 방식으로 진행할경우

초기에는 왼쪽에서 세로로 한번 자르고, 2번째에는 1열을 제외하고 1행의 C-1개의 칸을 자르고,

3번째에는 C열의 R-1개의 칸을 자르고

4번째에는 R행의 C-2개의 칸을 자르고..처럼 진행할경우 O(R+C)로 시간복잡도를 확 줄일 수 있다.

 

O(R)이나 O(1)만에 답을 구할 수 있을지는 잘 모르겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int r, c, k, dy[4] = {1, 0, -1, 0}, dx[4] = {0, 1, 0, -1};
bool visited[1001][1001];
void f(int d, int x, int y, int dir) {
    if (d == k) {
        cout << x << " " << y;
        exit(0);
    }
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    if (ny >= 1 && nx >= 1 && ny <= r && nx <= c && !visited[nx][ny]) {
        visited[nx][ny] = true;
        f(d + 1, nx, ny, dir);
    } else {
        dir++;
        if (dir == 4) dir = 0;
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        visited[nx][ny] = true;
        f(d + 1, nx, ny, dir);
    }
}
int main(void) {
    cin >> c >> r >> k;
    if (r * c < k) {
        cout << 0;
        return 0;
    }
    visited[1][1] = true;
    f(1, 1, 1, 0);
    return 0;
}