알고리즘 풀이/백준(Boj)
백준(BOJ) 16957번 체스판 위의 공
100win10
2020. 1. 16. 14:09
문제 : https://www.acmicpc.net/problem/16957
16957번: 체스판 위의 공
크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙에 의해서 자동으로 움직인다. 인접한 8방향 (가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다. 그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다. 공의 크기는 매우 작아서, 체스판의 한 칸 위에 여러 개의 공이 있을
www.acmicpc.net
풀이 :
각각의 좌표는 8방향을 탐색하면서 가장 작은 좌표를 찾는다. 그리고 가장 작은 좌표를 부모 좌표로
나타낸다. 이때 findParent 함수는 최종 부모 좌표를 빠른 시간에 찾도록 해준다.
그 후 각각의 좌표가 나타내는 최종 부모 좌표에 +1을 해준다.
출력한다.
코드 ( C++ )
