[SWEA / Java] 1861 : 정사각형 방

문제

난이도 D4

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE&problemTitle=%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95+%EB%B0%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

풀이

1. 방에 들어있는 숫자와 해당 방에서 연속으로 갈 수 있는 방의 개수를 변수로 갖고 있는 room class를 생성해주었다. (난 배열을 두개 만드는 것보다 새로운 클래스를 만들고 그 클래스 type으로 배열을 만드는게 좋다)
2. search 함수를 만들고, 4방을 탐색하며 현재 값보다 1이 더 큰 이웃한 방이 있으면 search를 재귀로 다시 불러 넘어간다
3. 다른 방으로 넘어갈 때마다 해당 방의 count를 올려준다
4. 더이상 갈 방이 없으면 break하여 돌아온다

코드

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

public class SW1861 { // 정사각형 방

	static int tc, N, count;
	static StringTokenizer st;
	static room[][] map;
	static int[][] dir = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		tc = Integer.parseInt(in.readLine());

		for (int t = 1; t <= tc; t++) {

			sb.append("#").append(t).append(" ");
			N = Integer.parseInt(in.readLine());
			map = new room[N][N];

			for (int i = 0; i < N; i++) {// map에 room type의 값을 넣기
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < N; j++) {// value와 count=1으로 값 채우기
					map[i][j] = new room(Integer.parseInt(st.nextToken()), 1);
				}
			}
			
			room result = new room(); // val=0, cnt=0으로 초기화 됨
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					count = 0;
					search(i, j);
					map[i][j].cnt += count;
					
					if (result.cnt < map[i][j].cnt) {
						result = map[i][j];
					} else if ((result.cnt == map[i][j].cnt) 
                   				 && result.val > map[i][j].val) {
						result = map[i][j];
					}
				}
			}

		
			sb.append(result.val).append(" ").append(result.cnt);
			System.out.println(sb);
			sb.setLength(0);

		} // tc
	}// main

	public static void search(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			while (dx >= 0 && dx < N && dy >= 0 && dy < N 
					&& map[dx][dy].val == map[x][y].val + 1) {
				count++;
				search(dx, dy);
				break;
			}
		}
	}

	static class room {
		int val, cnt;

		public room() {
			this.val = 0;
			this.cnt = 0;
		}

		public room(int val, int cnt) {
			this.val = val;
			this.cnt = cnt;
		}

	}
}// class

 

느낀점

• 전체 방에 대하여 계속해서 재귀를 호출하고 사방을 탐색하기 때문에 비효율적인 부분이 있다. DP를 사용해서 이미 구한 count에 대해서는 값을 저장해두고, 이웃한 방에서 해당 방을 탐색할 때 DP 배열에 저장한 값만 불러온다면 더 효율적으로 구현할 수 있을 것 같다. 다음에 DP를 사용해서 다시 풀어볼 것.