[백준] 20118번: 호반우가 길을 건너간 이유

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545

2020 경북대학교 Goricon

문제 주소 : www.acmicpc.net/problem/20118

20118번: 호반우가 길을 건너간 이유

 

문제 확인

 

언뜻 보면 그래프 탐색 혹은 dp 문제처럼 볼 수 있지만 단순한 아이디어 문제입니다.

XOR연산의 특징인 a xor a = 0임을 이용하고 최대 K가 2*(N+M)이며 이를 넘지 않는 길을 찾는 것에 중점을 두면 됩니다. 이를 통해 하나의 방법을 생각할 수 있습니다.

대각선으로 움직이게 되면 가장 빠르게 원점에 가까워 질 수 있으므로 두 가지 스텝으로 나누어 길을 찾습니다

 

풀이

 

1. 대각선으로 최대한 움직일 수 있을 때 까지 움직인다. -> n, m 중 작은 수에서 2로 나눈 횟수만큼 움직임
2. n, m의 남은 수를 처리
3. n,m이 모두 짝수가 아닌 경우 최종 위치가 목적지가 아니므로 한번 더 이동이 필요함

대각선으로 움직인 후 남은 칸을 처리 해야 합니다.

먼저 가로와 세로 중 남은 칸을 2단위로 이동하는 방식으로 처리합니다.

n, m이 모두 남게 되면 아래와 같이 이동하여 마무리를 합니다. n, m 중 한 값이 남게 되면 남은 값을 통하여 목적지까지 이동을 합니다.

모든 경로는 왕복을 하여 xor 조건을 만족시켜 주어야 하기 때문에 답은 다음과 같이 나옵니다.

결과 : 1 2 1 2 3 4 3 4 5 6 5 6 7 8 7 8 9 10 9 10

K는 20이 되고 문제 조건인 2*(n+m)은 14*2 이므로 조건을 만족하게 됩니다.

 

이 방식을 이용하면 n과 m 중 큰 값을 max, 작은 값을 min으로 두면 경로의 길이는 min*2 + (max-min) * 2 + f가 되므로 2(m * n) 보다 작은 값이 나오게 됩니다. 이때 f는 n, m이 모두 짝수인 경우 탐색 종료지점이 목적지이기 때문에 0, 나머지 경우는 목적지까지 움직이는 길을 추가하여 4가 됩니다.

 

코드

#include <cstdio>
using namespace std;
void print(int cross, int move_down, int move_right, int t) {//t : 대각선, 가로세로 움직임이 끝난 후 목적지가 아니라면 경로수에 4를 추가로 더함
    printf("%d\n", ((cross + move_down + move_right) << 1) + t);
    for (int i = 0; i < cross; i += 2) {
        printf("%d %d\n%d %d\n", i, i, i + 1, i + 1);
        printf("%d %d\n%d %d\n", i, i, i + 1, i + 1);//대각선 경로 출력
    }
    int cx = cross - 1, cy = cross - 1;
    for (int i = cross; i < cross + move_down; i += 2) {
        printf("%d %d\n%d %d\n", i, cy, i + 1, cy);
        printf("%d %d\n%d %d\n", i, cy, i + 1, cy);//세로로 움직인 경우 출력
    }
    for (int i = cross; i < cross + move_right; i += 2) {
        printf("%d %d\n%d %d\n", cx, i, cx, i + 1);
        printf("%d %d\n%d %d\n", cx, i, cx, i + 1);//가로로 움직인 경우 출력
    }
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int cross = (n < m ? n : m) & 0x7ffffffe;//대각선으로 움직일 횟수
    int cx = cross - 1, cy = cross - 1;//대각선으로 움직인 후 남은 칸 수
    int move_down = (n-1-cx) & 0x7ffffffe, move_right = (m - 1 - cy) & 0x7ffffffe;//0, 1칸이 남을 때 까지 이동
    cx += move_down;
    cy += move_right;
    
    if (cx != n - 1 && cy != m-1) {//m, n 모두 남았을 때
        print(cross, move_down, move_right, 4);
        printf("%d %d\n%d %d\n", cx, cy + 1, cx + 1, cy + 1);
        printf("%d %d\n%d %d\n", cx, cy + 1, cx + 1, cy + 1);
    }
    else if (cx != n - 1) {//세로로 남은경우
        print(cross, move_down, move_right, 4);
        printf("%d %d\n%d %d\n", cx + 1, cy - 1, cx + 1, cy);
        printf("%d %d\n%d %d\n", cx + 1, cy - 1, cx + 1, cy);
    }
    else if (cy != m - 1) {//가로로 남은경우
        print(cross, move_down, move_right, 4);
        printf("%d %d\n%d %d\n", cx - 1, cy + 1, cx, cy + 1);
        printf("%d %d\n%d %d\n", cx - 1, cy + 1, cx, cy + 1);
    }
    else {//움직인 최종 위치가 목적지 일 때
        print(cross, move_down, move_right, 0);
    }
    
}