자유게시판

문제번호 원판돌리기 17822원판 돌리기문제 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판돌리기 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (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) (1, j)는 (2, j)와 ...소스코드알고리즘 분류구현, BFS문제 풀이* 시계 방향으로 원판을 돌리는 방법 (Rotate 함수)deque 를 활용하였다. 예를 들어 배열 1, 2, 3, 4 를 시계 방향으로 원판돌리기 회전을 하면 4, 1, 2, 3 이 되고 반시계 방향으로 회전을 하면 2, 3, 4, 1 이 되기 때문에 deque 를 사용하면 쉽게 돌릴 수 있을거라고 생각하였다.시계방향은 pop_back() 을 해준후 그것을 원판돌리기 다시 push_front() 해주고반시계방향은 pop_front() 해준후 그것을 push_back() 해주면 쉽게 배열을 회전시킬 수 있다.​* 인접한 숫자중 같은 숫자 찾아 0 으로 바꿔주는 함수 (BFS)BFS 를 활용하면 풀 수 있다.BFS 를 통해 인접한 원판돌리기 구역들을 모두 탐색해 나가면서 인접한 모든 영역 중 같은 숫자인 부분들을 0 으로 바꿔주고 방문처리를 해주어야 한다. 크게 cur_y 가 1(첫 배열) 일때, N일때로 나누고 (1일때는 윗쪽은 탐색할 수 없고 N 원판돌리기 일때는 아래쪽을 탐색할 수 없기 때문에) 그 다음에 세부적으로 next_x 가 -1 일때와 아닐때로 구분하여 배열을 연결시킬 수 있었다. 만약 한번이라도 같은 숫자를 찾았다면, true 를 마지막에 리턴시켜준다​* 인접한 숫자가 없을 원판돌리기 경우 평균값을 구해 원판을 업데이트 해주는 함수 (Check)평균값을 구할 때 주의해야 한다. 평균이 소수가 나올 수 있기 때문에 double 이 되어야 한다.따라서 비교해줄때 또한 비교값을 double 로 형변환을 해서 비교를 해주어야 원판돌리기 한다.