[SWEA] 1861. 정사각형 방

풀이

바로 아래 코드로 하게 되면 통과는 되지만 시간 복잡도가 매우 올라간다. 그래서 '다른풀이코드'처럼 가지치기가 필요하다.
memo배열을 통해 탐색했던 자리를 다시 탐색하지 않도록 했다.

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Scanner;
	
	/**
	 * 정사각형 방
	 * 
	 * @author multicampus
	 *
	 */
	public class Solution_1861_이광용 {
	
		static int[] dx = {0, -1, 0, 1};
		static int[] dy = {1, 0, -1, 0};
		static int[][] map;
		static int ansPos, ansMax, cnt, n, k, l;
		public static void main(String[] args) throws NumberFormatException, IOException {
			Scanner sc = new Scanner(System.in);
			int tc = sc.nextInt();
			for(int t = 1; t <= tc;t++) {
				ansPos = Integer.MAX_VALUE; //출발 해야하는 방의 번호
				ansMax = 0;
				//cnt = 1; //시작방 포함 
				n = sc.nextInt();
				map = new int[n][n];
				
				for(int i = 0; i < n; i ++) {
					for(int j = 0; j < n;  j ++) {
						map[i][j] = sc.nextInt();
					}
	
				}
				for(k = 0 ; k < n; k ++) {
					for(l = 0; l < n; l++ ) {
						dfs(k, l, 1); //모든 점에 대해서 탐색
					}
				}
				System.out.println("#" + t + " " + ansPos + " " + ansMax);
			}
		}
		public static void dfs(int x, int y, int cnt) {
				for(int i = 0; i < 4; i++) { //4방향 탐색
					 int nx = x + dx[i];
					 int ny = y + dy[i];
					 if(nx >= 0 && nx < n && ny >= 0 && ny < n  &&
							 map[x][y]+1 == map[nx][ny]) { //현재 위치값보다 1만큼 크다면
						 cnt++;
						 if(ansMax < cnt) {
							 ansMax = cnt; //갱신할 때
							 ansPos = map[k][l];
						 }
						 else if (ansMax == cnt) {
							 if(ansPos > map[k][l]) ansPos =map[k][l]; 
						 }
						 dfs(nx, ny, cnt);
						 cnt--;
					 }
				}
			}		
	}

다른 풀이 코드

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

/**
 * 30,208 kb 145 ms
 */

public class Solution_1861_ {

	static int N,MAX,start;
	static int map[][]; 
	
	static int dr[] = {-1,1,0,0};
	static int dc[] = {0,0,-1,1};
	static int memo[][]; //가지치기를 위한 카운트 메모  
	public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(in.readLine());
		StringTokenizer st = null;
		for(int t=1; t<=TC; ++t) {
			N = Integer.parseInt(in.readLine());
			map = new int[N][N]; 
			memo = new int[N][N]; 
			MAX = 0; 
			for(int i=0; i<N; ++i) {
				st = new StringTokenizer(in.readLine());
				for(int j=0; j<N; ++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			//end 
			int count = 0; 
			for(int i=0; i<N; ++i) {
				for(int j=0; j<N; ++j) {	
					if(memo[i][j]==0) { //출발 위치(i, j)를 기준으로 한번도 계산된 적이 없을 경우만 계산
						count = go(i,j); //방문횟수를 계산하는 메서드
						if(count>MAX) { 
							MAX = count;
							start = map[i][j];
						}else if(count==MAX) {
							if(start>map[i][j]) start = map[i][j];
						}
					}
				}
			}
			System.out.println("#"+t+" "+start+" " +MAX);
		}
		in.close();
	}

	/**
	 * 
	 * @param r : 출발 위치
	 * @param c
	 * @return : 방의 개수를 계산해서 리턴
	 */
	private static int go(int r, int c) {
		int nr,nc,res=0;
		for(int d=0; d<4; ++d) { //4방탐색
			nr = r + dr[d];
			nc = c + dc[d];
			if(nr>=0 && nr<N && nc>=0 && nc<N) { 
				if(map[nr][nc]==map[r][c]+1) { //정확히 나보다 1큰지 확인  
					res = go(nr,nc);//다음 방으로 이동하도록 재귀 호출 + 리턴값으로 res를 받는다. 
					break; //break하는 이유 !!!! : 어차피 나보다 1만큼 큰 수는 하나뿐이고 이미 사용함
				}
			}
		}
		//여기까지 내려왔다? 위에 상황만족x : 현재위치 기준 이동가능한 방 없음
		return memo[r][c] = res+1; //현재 카운팅한 res가 움직인 수(이동횟수)이기 때문에 방의 수는 +1해서 출발방까지 포함해야함
		//리턴으로 보냄!!!
	}
}