1861. 정사각형 방

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc 

SW Expert Academy

 

* dfs

시작~끝까지 각각 들어가서 탐색함

ex)

1 2

3 4

 

1. 1에 가서 4방탐색 next구함

2.if(범위안 && next와 -현재값==1)

       count++

       dfs(nextr,c)           //2번에 들어가서 다시dfs하면서 count세기 . 1과 연결된 조건맞는애들 각각bfs한다

                                    //조건에 맞는애가 없으면 return됨

 

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

public class Solution_1861_유동훈2 {
	// 상하좌우
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int count = 1;

	public static void main(String[] args) throws NumberFormatException, IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();	//답
		int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수

		for (int test_case = 1; test_case <= T; test_case++) 
		{
			int N = Integer.parseInt(br.readLine()); // N*N의 N 입력

			int[][] rooms = new int[N][N]; // 방 숫자 담을 배열

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					rooms[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			int room = Integer.MAX_VALUE; // 방에 적힌 번호
			int max = 0;	//최대값
			
			for(int i=0;i<N;++i)
			{
				for(int j=0;j<N;++j)
				{
					count=1;
					int temp=dfs(i,j,rooms);
					
					//최대값, 최대 방번호 갱신
					if(max<temp) 
					{
						max=temp;
						room=rooms[i][j];
					}
					
					if(max==temp) room=Math.min(room, rooms[i][j]);
				}
			}
			sb.append("#"+test_case+ " "+room+" "+max+"\n");

		}
		System.out.println(sb);
		br.close();
	}
	static int dfs(int r, int c, int rooms[][]) {
		for(int i=0;i<dr.length;++i)
		{
			int nr=r+dr[i];
			int nc=c+dc[i];
			
			if(nr>=0 && nr<rooms.length && nc>=0 && nc<rooms.length)
			{
				if(rooms[r][c]-rooms[nr][nc]==-1)
				{
					count++;
					dfs(nr,nc,rooms);
				}
			}
			
		}
		return count;
	}
}