[SWEA] 1861:정사각형 방 (Java 자바)

풀이 및 소스코드

 

문제를 보면, 구해야 하는 것이 갈 수 있는 방의 최댓값과 그 최댓값이 나올 때 출발 방의 번호이다.

따라서 출발하는 방 번호를 인덱스로 하는 c 배열을 만들어서 들릴 수 있는 방의 갯수를 넣어주었다.

예를들면 1번에서 출발할 때 5개의 방을 들릴 수 있다면,

c[1] = 5 이렇게 넣어주었다.

 

이 문제에서는 방을 타고 타고 타고 가는 것이므로 dfs 를 사용했다.

import java.io.*;
import java.util.*;

public class Solution {

	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static int cnt;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int[][] room;
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=t;tc++) {
			int n = Integer.parseInt(br.readLine());
			room = new int[n][n];
			
			for(int i=0;i<n;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<n;j++) {
					room[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int[] c = new int[n*n+1];
			int max = 0;
			int start_room = n*n; //처음출발하는방. 방 번호의 최솟값을 넣어줘야하므로 큰값을 넣어주장
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					cnt = 1;
					dfs(room, i, j, n, room[i][j]);
					c[room[i][j]] = cnt;
					if(cnt>=max) {
						if (cnt>max) {
							start_room = room[i][j];
							max = cnt;
						}
						else {
							if(start_room>room[i][j]) {
								start_room = room[i][j];
							}
						}
						
					}
				}
			}
			sb.append("#"+tc).append(" ").append(start_room+" ").append(max).append("\n");
		}
		System.out.println(sb);
	}
	public static void dfs(int[][] r, int x, int y, int N, int now_n) {
		for(int i=0;i<4;i++) {
			int nowx = x+dx[i];
			int nowy = y+dy[i];
			if((0<=nowx&&nowx<N)&&(0<=nowy&&nowy<N)&&(r[nowx][nowy]==now_n+1)) {
				cnt++;
				dfs(r, nowx, nowy, N, now_n+1);
			}
		}
	}

}