[baekjoon] 5573

산책

문제

상근이는 건강을 위해 산책을 하려고 한다.

상근이가 사는 마을은 아래 그림과 같이 가로 방향 도로가 (H+1)개, 세로 방향 도로가 (W+1)개가 바둑판 모양으로 배치되어 있다. 상근이네 집은 가장 왼쪽 위 교차로에 있으며, 이곳에서 산책을 시작한다.

(a,b)는 위쪽에서 a번째, 왼쪽에서 b번째에 있는 교차로이다. 예를 들어, 상근이네 집은 교차로 (1,1)에 있다.

상근이는 산책 경로가 매일 달라야 질리지 않고 산책을 할 수 있다고 생각한다. 따라서, (1,1)에서 (H,W)까지 H × W개 교차로에 오른쪽을 뜻하는 오 또는 아래를 뜻하는 아를 쓰고, 다음과 같은 규칙에 따라서 산책을 하기로 했다.

교차로에 쓰여 있는 문자가 오라면, 이 문자를 지우고 아를 쓴다. 그 다음에 오른쪽으로 진행한다. 만약, 교차로에 쓰여 있는 문자가 아라면, 이 문자를 지우고 오를 쓴뒤, 아래로 진행한다.

이렇게 산책을 하다가 가장 오른쪽이나 아래쪽 도로에 도착하면 산책을 종료한다.

상근이는 이런 방법으로 산책을 계속 한다면, N번째 산책 경로가 어떻게 될지 궁금해졌다. H, W와 각 교차로에 써놓은 글자가 주어졌을 때, N번째 산책 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107)

둘째 줄부터 H개 줄에는 W개 정수가 주어진다. 이 정수는 상근이가 교차로에 써 놓은 문자의 정보이다. 0은 아래쪽을 의미하는 '아', 1은 오른쪽을 의미하는 '오'이다.

출력

N번째 산책에서 산책을 종료하는 교차로가 (i,j)라고 할 때, i와 j를 공백으로 구분하여 출력한다.

예제 입력

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

예제 출력

1 5

힌트

풀이

힌트를 보니까 격자 경로의 수(?)가 생각났다.

중학교인가.. 초등학교때 했던 1111111

출발 지점, 회수, 방향이 정해져있기때문에 다음 지점에 몇 번 방문할지를 예측할 수 있지 않을까라는 생각이 들었다.

첫 지점(0, 0)에서 갈 수 있는 두 곳은 (0, 1), (1, 0)이다.

첫 방향이 오른쪽이기 때문에 (1, 0)은 3회, (0, 1)은 2회 방문하게 된다.

 

그럼 (1, 1)은 몇 번 방문하게 될까?

 

(1, 0)에서 (1, 1)을 가게 되는 횟수 2 + (0, 1) 에서 (1, 1)을 가게 되는 회수 1 = 3

이런 식으로 각 칸마다 방문횟수를 계산하면 N번째 산책할 때 산책경로의 모양을 알 수 있게 된다.

N번째에 산책을 진행해야 하기 때문에 방문횟수를 구할 때 시작지점 회수는 N-1로 해준다.

 

#include <iostream>
#define down 0
#define right 1

using namespace std;

int H, W, N;
int **board, **dp;

void input()
{
    cin >> H >> W >> N;

    board = new int *[H];
    for (int i = 0; i < H; i++)
    {
        board[i] = new int[W];
        for (int j = 0; j < W; j++)
        {
            cin >> board[i][j];
        }
    }
}
bool isOut(int x, int y)
{
    if (x == W || y == H)
        return true;
    else
        return false;
}

void calcVisitCount(){
    int direction[4] = {1,0,0,1};

    dp = new int *[H];
    for (int i = 0; i < H; i++)
    {
        dp[i] = new int[W];
        for (int j = 0; j < W; j++)
        {
            dp[i][j] = 0;
        }
    }

    dp[0][0] = N - 1;
    for (int y = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++)
        {
            for (int i = 0; i < 2; i++)
            {
                int nx = x + direction[i * 2 + 1];
                int ny = y + direction[i * 2];
                int cnt = dp[y][x] / 2;

                if (isOut(nx, ny))
                    continue;

                if (board[y][x] == down && i == 0 && dp[y][x] % 2 != 0)
                    cnt++;
                if (board[y][x] == right && i == 1 && dp[y][x] % 2 != 0)
                    cnt++;

                dp[ny][nx] += cnt;
            }
        }
    }
}

void changeBoard(){
    for(int y = 0; y < H; y++){
        for(int x = 0; x < W; x++){
            board[y][x] += dp[y][x] % 2;
            board[y][x] %= 2;
        }
    }
}

void solve()
{
    calcVisitCount();
    changeBoard();

    int x = 0, y = 0;
    while (!isOut(x, y))
    {
        if (board[y][x] == down)
            y++;
        else if (board[y][x] == right)
            x++;
    }

    cout << y + 1 << " " << x + 1;
}

int main()
{
    input();
    solve();
}