정사각형 방 | SWEA

문제

💥 문제 바로가기

문제	레벨	정답률
1861. 정사각형 방	D4	63%

My Code

package swea;
import java.util.*;

public class swea_1861_서정후 {
	// 방향 설정
	private static final int[] dx = { -1, 1, 0, 0 };
	private static final int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testCase = sc.nextInt();

		for (int test_case = 1; test_case <= testCase; test_case++) {
			int N = sc.nextInt();
			int[][] arr = new int[N][N];
			int[][] memo = new int[N][N];

			// 배열 입력받기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}

			int maxCnt = 0;
			int startNum = Integer.MAX_VALUE;

			// 배열 전체 탐색
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					int cnt = search(N, i, j, arr, memo);
					
					// 데이터 갱신하기
					if(cnt > maxCnt || (cnt == maxCnt) && arr[i][j] < startNum){
						maxCnt = cnt;
						startNum = arr[i][j];
					}
				}
			}
			
			System.out.println("#" + test_case + " " + startNum + " " + maxCnt);
		}
	}

	// 상하좌우 이동
	public static int search(int N, int x, int y, int[][] arr, int[][] memo) {
		//이미 계산된 경우
		if(memo[x][y] != 0) {
			return memo[x][y];
		}
		
		int maxMove = 1;
		
		// 방 이동
		for(int d = 0; d<4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			//이동가능한지 확인하기
			if(nx >= 0 && nx < N && ny >= 0 && ny < N && arr[nx][ny] == arr[x][y] + 1) {
				maxMove = Math.max(maxMove, 1+search(N, nx, ny, arr, memo));
			}
		}
		
		//메모에 저장하기
		memo[x][y] = maxMove;
		return maxMove;
	}

}

전체 로직

1. 모든 Array를 돌기
2. 상하좌우 보고 차 계산
   (이동할 방) - (현재 방) = 1 이면 cnt++
   위치 이동해서 반복 (재귀 사용)
3. 전체를 돌면서 cnt를 비교하고, 큰 값을 cnt에 저장
   만약 cnt가 같다면 숫자가 작은걸 pick!
4. 숫자와 cnt를 출력

---

아직 방향 문제가 익숙하지 않아서 오래걸리고, 조금만 복잡해지면 막히는 경향이 있어서 과제가 나온김에 비슷한 문제를 많이 풀어봐야겠다.