[백준] JAVA - 16926. 배열 돌리기 1

2차원 배열이 주어졌을때 배열을 R번 회전시킨 결과를 출력하는 문제입니다.

 

알고리즘 분류에는 구현이라고 정의되어있지만 요즘 재귀,DFS 문제를 계속 연습하는 중이라 이 문제도 재귀적으로 풀어보고 싶어서 도전했습니다!

 

1. 배열을 회전시킬 껍데기 개수를 구한다. <- 가로 세로 중 작은값 나누기 2 (Math.min(row,col)/2)

2. 회전 함수를 R번 반복시킨다.

3. 회전 함수의 y,x는 회전을 하는 껍데기의 가장 왼쪽 위 좌표입니다. beforeVal 은 새롭게 밀어 넣을 이전 값입니다. 만약 회전을 4방향으로 모두 다 한 상태이고 현재위치가 시작위치로 다시 돌아왔다면 리턴합니다.

3-1. 그렇지 않다면, dir방향으로 전진 할 수 있는 경우일때  다음 좌표인 ny와 nx의 범위를 체크해야하는 조건식이 필요합니다. 이때 ny와 nx의 범위는 해당 껍데기의 번호를 뺀것보다 작아야 하고 껍데기의 번호보다 커야 합니다. 이 경우를 만족시킬 경우 다음 단계로 들어갑니다.

3-2. dir방향으로 전진을 모두 다 했으므로 방향을 바꿔주는 경우입니다. 이때는 다음방향 direction을 1증가시킨뒤 ny, nx를 업데이트 시켜야 합니다. 이렇게 한 후에, 다음 단계로 들어갑니다.

 

Java 코드 - 재귀 구현

package com.ssafy.off;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baekjoon_16926_배열돌리기1 {
	static int[][] map;
	static int[] dy = {1,0,-1,0}; // 아래 -> 오른쪽 -> 위 -> 왼쪽
	static int[] dx = {0,1,0,-1}; // 아래 -> 오른쪽 -> 위 -> 왼쪽
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] info = br.readLine().split(" ");
		int N = Integer.parseInt(info[0]);
		int M = Integer.parseInt(info[1]);
		int R = Integer.parseInt(info[2]);
		
		map = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int group = Math.min(N, M) / 2;
		while(R-- > 0) {
			for (int i = 0; i < group; i++) {
				dfs(i, i, 0, i, map[i][i+1]);
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				sb.append(map[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.print(sb);

	}
	/**
	 * 배열 n번 돌린다.
	 * groupCnt : 밖에서부터 돌릴때 그룹 번호 (껍데기번호 0부터)
	 * */
	private static void dfs(int y, int x, int dir, int groupCnt, int beforeVal) {
		//base case
		if(dir>=3 && (y == groupCnt && x == groupCnt)) return; // 한바퀴 다 돌고 다시 처음위치로왔을때 종료
		
		int now = map[y][x];
		map[y][x] = beforeVal;
		
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		
		//dir방향으로 계속 전진가능할때
		//높이가 5 0 123 4 껍데기번호만큼 빼야 범위나옴
		if(ny >= groupCnt && ny < map.length-groupCnt && nx >= groupCnt && nx < map[0].length-groupCnt) {
			dfs(ny, nx, dir, groupCnt, now);
		}
		//dir바꿔줘야할때
		else {
			int nextDir = dir+1;
			ny = y + dy[nextDir];
			nx = x + dx[nextDir];
			dfs(ny, nx, nextDir, groupCnt, now);
		}
		
	}

}