(JAVA) 백준 17822번 : 원판 돌리기

https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

 

 

 

시뮬레이션 + DFS 문제.

 

삼성 기출 SW 문제집 문제 중 하나.

 

 

 

아래 질문에 대해 해결 방법을 찾아 구현하면 쉬운 문제이다.

 

 

  -  원판을 나타내는 방법?

  

  -  인접한 것을 확인하는 방법?

 

  -  원판을 회전함에 따라 원판 내 숫자 순서도 바뀌게 하는 방법?

 

 

 

해결 방법은 간단하다.

 

 

2차원 int 배열을 사용하는 것

*** y좌표 : 반지름

*** x좌표 : 12시 방향을 시작점으로 시계방향으로 존재하는 숫자 순서

 

 

 

 

나머지 구현 사항은 아래 매커니즘과 소스코드를 참고하면 된다.

 

 

매커니즘

---

1. 2차원 int 배열에 input 값 집어넣기. + 회전시키는 경우들을 순서대로 LinkedList에 넣기.

 

 

 

2. 원판 돌릴 시 돌린 칸 만큼 배열 내 값 변경.

  -> 시계방향 : 인덱스 + 1

  -> 반시계방향 : 인덱스 - 1

 

*** 이 때, Circular Queue(원형 큐) 처럼 순환하도록 구현해야 함.

 

 

 

+) 처음에 이런 방식으로 해결하려 했는데, 실패함.

 

ex. 시계 방향으로 2칸씩 이동시키는 경우

 

index  |  0  |  1  |  2  |  3  |  4  |

num   |  5  |  4  |  3  |  2  |  1  |

 

 

0 + 2 = 2

0의 num을 2로 이동.

2에서 다시 시작.

 

2 + 2 = 4

2의 num을 4로 이동.

4에서 다시 시작.

 

4 + 2 % 5 = 1

4의 num을 1로 이동.

1에서 다시 시작.

 

1 + 2 = 3

1의 num을 3으로 이동.

3에서 다시 시작.

 

3 + 2 % 5 = 0

3의 num을 0으로 이동.

출발 지점인 0과 일치하므로 종료.

 

 

*** 위 방법으로 잘 될 것 같았지만, 예외가 있었다.

  ->  전체가 4인 배열에서 시계 방향으로 2만큼 이동시키는 경우, 0 -> 2 -> 0 -> 2 무한 반복.

 

 

그래서 결국

 

별도의 Array를 하나 더 만들고,

 

원판 Array를 0부터 끝까지 for문으로 탐색하며 하나씩

 

이동시키는 칸 만큼 이동한 index 에 해당하는 별도 Array에 이동 전 값을 넣는다.

 

 

다 완료되면 별도 Array를 copy한다.

 

*** 주석 처리한 부분이 처음에 했던 잘못된 방법이고,

주석 처리가 되어있지 않은 부분은 위에 적었던 대로 정상 작동하는 방법이다.

 

 

 

 

3. DFS를 통해 모든 자기 주위(상,하,좌,우) 의 값이 자기와 같으면 값을 0으로 변경

  -> 이 때, 모든 값이 하나라도 같은게 없는지 boolean 으로 체크

  -> 하나라도 같은게 없다면, 모든 값의 평균과 각 값을 하나씩 비교해가며 조건에 따라 값을 변경시킨다.

 

*** 평균보다 크거나 작은 경우에만 값을 변경시키고, 같을 때는 변경시키지 않으므로 이점에 유의하며 조건문을 사용한다.

 

 

 

 

 

 

더 자세한 사항은

 

소스코드(+ 주석) 을 참고해주세요.

 

 

 

감사합니다.

 

소스코드

---