백준 17822번 원판 돌리기 :: 마이구미

이 글은 백준 알고리즘 문제 17822번 "원판 돌리기" 를 풀이한다.
2019 삼성 SW 테스트 문제 중 하나이다.
단순히 시뮬레이션으로 풀 수도 있으나, DFS 또는 BFS 를 활용할 수 있는 문제이다.
DFS, BFS - https://mygumi.tistory.com/102
문제 링크 - https://www.acmicpc.net/problem/17822

 

 

본인은 처음 이 문제를 접근할 때, 많은 고민을 했다.

그런데 사실 이 문제는 사실 정답률에 비해, 크게 어렵지도 복잡하지도 않다.

그 이유는 고민할 게 크게 없었고, 테스트 케이스도 작아서, 어떻게 구현해도 시간 초과를 초래하지 않을 거라 판단했다.

그래서 "어떤 함정이 있을까?" 라는 의심에 시간을 좀 썼다.

사실 의심할 건 크게 없고, 이해하고 풀면 크게 어렵지 않은 문제이다.

 

문제는 복잡해보일 수도 있으나, 그림으로 친절히 원을 알려주었다.

결국 원형으로써, 같은 원판에서 하나의 수는 양쪽을 인접할 수 있다.

다른 원판끼리는 같은 수직 또는 수평선에 있으면 인접하다고 볼 수 있다.

문제에서 알려주는 수의 위치를 빨간색은 다른 원판, 파란색은 같은 원판을 의미한다.

 

(i, 1)은 (i, 2), (i, M)과 인접하다.
(i, M)은 (i, M-1), (i, 1)과 인접하다.
(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
(2 ≤ j ≤ M-1)(1, j)는 (2, j)와 인접하다.
(N, j)는 (N-1, j)와 인접하다.
(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

 

단순히 하나를 기준으로 왼쪽, 오른쪽을 인접하다고 보면서, 끝과 끝(양쪽) 도 인접하다고 본다. (2 <= j <= M - 1)

원판을 배열로 표현하고, 인접하는 경우들을 그림으로 나타내면 다음과 같다.

 

 

그리고 각 원판은 회전하게 되고, 그 후에는 인접하면서 수가 같은 것을 찾게 된다.

있으면 모두 지우고, 하나도 없는 경우 각 수는 빼거나 더하게 된다.

 

인접하면서 수가 같은 것을 모두 찾는다.
그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

 

결국 구현 순서는 다음과 같다.

 

1. 원판을 돌린다.
2. 같은 원판에서 각 수를 기준으로 인접한 수들을 탐색한다.
3. 다른 원판끼리 인접한 수들을 탐색한다.
4. 인접한 경우의 존재 여부에 따라, 수들을 업데이트한다.

 

위 순서를 반복하면 된다.

주의할 점은 다음과 같다.

 

1. 원판의 회전방향은 시계 방향과 반시계 방향으로 분류된다.
2. 같은 원판에서 끝과 끝도 인접하다고 본다.
3. 원판을 회전할 때 배수 간격으로 회전한다. ex) 2 => 2, 4, 6, 8, 10번째 원판 돌린다.
4. 평균을 구하는 과정 나눗셈이 들어가기 때문에, 소수점까지 고려해야한다.
5. 평균을 구하고 더하고 빼는 과정에서 평균과 수가 같은 경우에는 변화하지 않는다.

 

여기서 사실 본인은 3번을 실수해서 개고생했다.

배수를 정확히 더해서 원판을 회전 시켜줘야한다.

 

for(int i = x; i <= N; i *= x;) {...}  // 잘못된 방식 2 4 8 16 32 ...

for(int i = x; i <= N; i += x;) {...} // 맞는 방식 2 4 6 8 10 12 ...

 

이 문제는 사실 그냥 풀어도 되지만, 웬만하면 dfs, bfs 로도 풀어보면 좋을 것 같다.

일반적인 BFS 를 활용하면 왼쪽, 위쪽, 오른쪽, 아래쪽을 탐색할 것이다.

이것은 오른쪽과 왼쪽은 같은 원판을 의미할 것이고 위쪽과 아래쪽은 다른 원판을 가리킬 수 있게 된다.

그리고 2번 과정만 추가해주면 된다.

 

static int[] dx = { -1, 0, 1, 0 }; // 왼쪽 위쪽 오른쪽 아래쪽
static int[] dy = { 0, -1, 0, 1 };
for (int i = 0; i < size; i++) {
    Point p = q.poll();
    for (int j = 0; j < 4; j++) {
        int nx = dx[j] + p.x;
        int ny = dy[j] + p.y;

        // 첫번째 요소인 경우, 왼쪽의 인접하는 수를 위해 m - 1 인덱스로 교체.
        if (j == 0 && p.x == 0) {
            nx = m - 1;
        }

        // 마지막 요소인 경우, 오른쪽의 인접하는 수를 위해 0 인덱스로 교체.
        if (j == 2 && p.x == m - 1) {
            nx = 0;
        }

        if (0 <= nx && nx < m && 0 <= ny && ny < n) {
            if (map[ny][nx] == p.v) {
                map[p.y][p.x] = 0;
                map[ny][nx] = 0;
            }
        }
    }
}

 

첫번째 요소의 경우, 왼쪽을 가리키는 인덱스는 -1 이다.

가리키는 인덱스 -1 을 배열의 마지막 인덱스를 가리키게 해주면 된다.

마지막 요소도 같은 맥락이다.

 

전체 코드는 Github 을 통해 참고하면 된다.

https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/17822.java