[SWEA] 1861 정사각형 방

1861 정사각형 방

난이도 : D4
유형 : 구현

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

문제

N2개의 방이 N×N형태로 늘어서 있다.

위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N2 이하의 수 Ai,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다.

당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.

물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.

처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 103)이 주어진다.

다음 N개의 줄에는 i번째 줄에는 N개의 정수 Ai, 1, … , Ai, N (1 ≤ Ai, j ≤ N2) 이 공백 하나로 구분되어 주어진다.

Ai, j는 모두 서로 다른 수이다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다.

이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.

풀이

단순 구현이다. 상하좌우로 이동할 수 있는 dx,dy를 이용하여 탐색하면서 가장 많은 방을 이동할 수있는 방 번호를 저장해놓으면서 반복문을 돌린다.
가장 많은 방을 이동할 수 있는 횟수가 같으면 방 번호를 비교해서 더 낮은 방번호를 변수에 저장해주는 방식으로 구현하면 된다.

코드

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

/**
 * SWEA_1861_D4_정사각형 방
 * @author mingggkeee
 * 구현
 */

public class SWEA_1861 {
	
	static int [][] map;
	static int N, T;
	static int answer = Integer.MAX_VALUE;	// 정답 방
	static int maxCount, compareCount;
	static int[] dx = {0, 1, -1, 0};
	static int[] dy = {1, 0, 0, -1};	// 남 동 서 북 
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		T = Integer.parseInt(br.readLine()); 	// 테스트 케이스 받기
		
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			// 정보 입력 받기
			for(int r=0; r<N; r++) {
				st = new StringTokenizer(br.readLine());
				for(int c=0; c<N; c++) {
					map[r][c] = Integer.parseInt(st.nextToken());
				}
			}
			search();
			bw.write("#"+t+" "+answer+" "+maxCount+"\n");
		}
		
		br.close();
		bw.flush();
		bw.close();
		
	}
	
	public static void search() {
		maxCount = 1;
		for(int r=0; r<N; r++) {
			for(int c=0; c<N; c++) {
				compareCount = 1;
				int nx = c;
				int ny = r;
				while(true) {
					int count = 0;
					for(int i=0; i<4; i++) {
						if(nx + dx[i] < N && nx + dx[i] >=0 && ny + dy[i] < N && ny + dy[i] >=0 && map[ny + dy[i]][nx + dx[i]] - map[ny][nx] == 1) {
							compareCount++;
							nx = nx + dx[i];
							ny = ny + dy[i];
							count++;
							break;
						}
					}
					if(count == 0) {
						break;
					}
					
				}
				if(compareCount > maxCount) {
					answer = map[r][c];
					maxCount = compareCount;
				} else if (compareCount == maxCount) {
					if(answer > map[r][c]) {
						answer = map[r][c];
					}
				}
				
			}
		}
		
		
	}
}