[백준] 17406번: 배열 돌리기 4

문제 https://www.acmicpc.net/problem/17406

풀이

이 문제를 풀어나간 순서를 간단히 말하자면 다음과 같다.

1. 연산 순서 정하기

2. 회전 연산하기

3. 배열값 구하기

 

 

1. 연산 순서 정하기

회전 연산이 여러개면, 연산을 수행한 순서에 따라 배열이 달라지기 때문에 연산 순서 조합을 모두 구해야한다.

연산은 최대 6개이기때문에 배열을 미리 만들어놔서 입력받을때 배열에 차례로 저장해두었다.

배열에 연산을 미리 저장해둔 이유는 배열의 인덱스를 이용하여 연산 순서 조합을 구하기 위함이다!

연산순서는 dfs(백트래킹) 방법으로 구했다.

 

2. 회전 연산하기

제일 많은 시간이 걸렸던 부분.. [SWEA] 1954번: 달팽이 숫자 문제를 연습한다면 좋을 것 같다..

일단, 1번에서 정한 연산 순서에 따라 연산을 순서대로 진행하면된다.

연산에 따라, 왼쪽위좌표 (sx, sy)와 오른쪽아래좌표(ex, ey)를 미리 구해놓는다.

방향을 의미하는 d변수도 따로 둔다. 0은 동쪽, 1은 남, 2는 서, 3은 북쪽을 가리킨다고 내가 맘대로 정해두었다.

while문을 돌면서 현재 방향에 맞게 다음 좌표 (nx, ny)를 구하고 그 좌표가 (sx, sy), (ex, ey)를 넘어가지 않는 선에서

swap을 진행한다. 경계값에 닿으면 방향을 바꿔주는 등 여러가지 작업들을 해주면된다..(구현해보는수밖에ㅠㅠ)

동남서북을 다 돌고 현재 좌표가 (sx, sy)에 도달했으면 안쪽으로 들어가준다. (sx+1, sy+1), (ex-1, ey-1) 이렇게!

만약 이 두점이 같은 점이거나 거리차이가 1일 경우 while문을 탈출해주었다

(그런데.. 거리차이가 1일때도 (가로세로2일때) 회전을 해야되는데..? 이상해서 두점이 같을 때만 break를 해주었더니 그래도 통과한다.. 이부분 뭔가 이상ㅠㅠ)

 

3. 배열값 구하기

모든 연산을 마치고 난후 배열값을 구한다.

 

** 힘들었던 점

1. 평소에 배열을 0베이스로 하다가 이 문제는 1베이스로 되어있어서 실수를 많이 했다

2. 배열을 가지고 노는 건 아직 빨리빨리 되지 않는다

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/java/17406.java

결과

**추가

깃헙 코드에는 추가되어있지 않지만 출력부분이 달랑 하나인데도 불구하고 StringBuilder를 사용했더니 4ms가 줄었다.