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

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

문제

정사각형 방 문제 링크

문제의 저작권은 SW Expert Academy에 있습니다

입력

2
2
1 2
3 4
3
9 3 4
6 1 5
7 8 2

출력

#1 1 2
#2 3 3

접근 방식

1. 전역변수로 maxMoveCnt와 moveCnt를 만들고 dfs를 돌리면서 움직인 만큼의 moveCnt를 maxMoveCnt와 비교하여 크거나 같을 시에 대한 조건을 구현한다

코드

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

public class Solution {

	
	static int n;
	static int matrix[][];
	static boolean visited[][];
	static int deltas[][] = {{-1,0},{0,1},{1,0},{0,-1}};
	
	static int moveCnt; // 특정 위치에서 움직인 수
	static int maxMoveCnt; // 특정 위치에서 움직인 최대 수 
	static int minValue; // 특정 위치에서 움직인 수가 최대일 때 처음 출발했던 위치의 값
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= T ; tc ++) {
			// 입력
			n = Integer.parseInt(br.readLine());
			
			matrix = new int[n][n];
			visited = new boolean[n][n];
			
			for(int i=0;i<n;i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int j=0;j<n;j++) {
					matrix[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			
			// dfs 탐색

			// 초기화
			maxMoveCnt = 0;
			minValue = n*n+1;
			
			// 배열 탐색하여 dfs 실행
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if (visited[i][j] == false) {
						moveCnt = 1;
						dfs(i,j);
						
						// 이번 위치에서 움직인 거리 값이 최대일 경우 
						if(maxMoveCnt < moveCnt) {
							maxMoveCnt = moveCnt;
							minValue = matrix[i][j];
						}
						// 이번 위치에서 움직인 거리 값이 전과 같을 경우
						else if(maxMoveCnt == moveCnt) {
							minValue = Math.min(minValue, matrix[i][j]);
						}
						
						
					}
				}
			}
			
			sb.append("#"+tc+" "+minValue+" "+maxMoveCnt+"\n");
			
			
		}
		System.out.println(sb);
	}
	
	public static void dfs(int i, int j) {
		visited[i][j] = true;
		
		int nowValue = matrix[i][j];
		
		for(int deltaIdx = 0; deltaIdx<4; deltaIdx++) {
			int nextI = i + deltas[deltaIdx][0];
			int nextJ = j + deltas[deltaIdx][1];
			
			if(nextI < 0 || nextI >= n || nextJ < 0 || nextJ >= n || matrix[nextI][nextJ] - nowValue != 1) continue;
			moveCnt++;
			dfs(nextI,nextJ);
		}
		
	}

}