| 2 초 | 512 MB | 2122 | 823 | 598 | 38.309% |
문제
크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다.
체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙에 의해서 자동으로 움직인다.
- 인접한 8방향 (가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다.
- 그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다.
공의 크기는 매우 작아서, 체스판의 한 칸 위에 여러 개의 공이 있을 수 있다. 체스판의 상태가 주어진다. 공이 더 이상 움직이지 않을 때, 각 칸에 공이 몇 개 있는지 구해보자.
입력
첫째 줄에 체스판의 크기 R, C가 주어진다. 둘째 줄부터 R개의 줄에 체스판에 적혀있는 정수가 주어진다.
출력
총 R개의 줄에 걸쳐서 체스판에 적힌 정수를 출력한다.
제한
- 1 ≤ R, C ≤ 500
- 0 ≤ 체스판에 적힌 정수 ≤ 300,000
예제 입력 1 복사
3 3
1 3 4
5 6 7
8 9 2
예제 출력 1 복사
6 0 0
0 0 0
0 0 3
풀이 아이디어
칸마다 8방향으로 가장 작은 정수 값으로 가다보면 어느 한 지점에서 정지하게 된다.
각 칸마다 정지하게 지점을 찾아서 카운트 +1해주면 된다.
칸마다 dfs를 해버리면 모든 칸 O(n^2) * dps O(n^2) 으로 O(n^4)가 되기 때문에 브루트 포스는 지양하며
각칸의 정수 값 변화가 없기 때문에 칸마다 단 한번만 계산하고 이미 방문한 칸이라면
DP를 통해서 값을 리턴하는 식으로 풀면 된다.
시행 착오
초반에 8방향을 4방향으로 착각하고 푼 것 의외에는
많이 본 유형이라서 한번의 트라이로 풀렸다.
최적화 해보기
유니온 파인드를 쓴 사람들과 분들이랑 프로그램 속도가 2배 차이 나길래
그렇게 차이나는가 했는데 입출력 단축 코드를 사용하니 다른 분들이랑 비슷하게 나왔다.
각 항목을 단 한번만 탐색하기 때문에 O(N^2)으로 푼셈인데
N^2의 데이터를 처리하는데
데이터의 크기보다 더 빠르게 풀 순 없을 것 같다.
'코딩 공부 > 백준' 카테고리의 다른 글
| [백준] 1082 방 번호 (1) | 2024.12.18 |
|---|---|
| 백준 1781) 컵라면 C++ (1) | 2023.10.28 |