/ SWEA

SWEA_1861_정사각형 방_JAVA

문제 : 정사각형 방

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_1861_정사각형 방

접근 방식

2차원 배열을 4방탐색 하면서, 현재 위치의 값보다 +1 되어있는 값이 있을 경우 그 방향으로 이동한다. 이것을 반복하다가 더 이상 이동할 수 없는 상태가 된다면, 지금까지 이동한 횟수의 최댓값 + 최대일 경우 이동한 초기위치의 값을 출력하는 문제이다.

이동한 횟수의 최댓값이 같을 경우에는 초기위치의 더 작은 값을 출력한다.

풀이 방법

  1. 방향 단위배열 dir을 선언한다. dir은 상,하,좌,우 4방향의 단위벡터를 가지고 있다.

  2. 2차원 배열의 길이(N)를 읽어들여 N*N 배열을 생성하고, 생성한 배열에 주어진 값을 할당한다. StringTokenizer를 이용한다.

  3. N*N만큼 반복한다. (for문 i,j)

  4. 초기위치는 i,j이다. 변동할 위치는 x,y이고, 체크할 위치는 dx,dy로 잡는다.

  5. dx, dy는 각각 x,y에서 단위벡터만큼 더한 값을 가진다.

  6. While문으로 계속해서 반복하며 dx, dy를 비교하며 4방탐색을 한다. 배열의 범위를 벗어나지 않고, 해당 위치의 값이 기존 위치의 값보다 정확히 1 크다면 좌표를 이동한다. (x = dx, y = dy) 그 후 카운트를 1 증가시켜준다.(이동했으므로)

  7. 4방 탐색이 이루어지기 전과 후의 카운트 변화 추이를 비교한다. 만약 카운트가 증가되지 않았다면 더 이상 움직일 곳이 없다는 뜻이기 때문에 추가 탐색을 종료한다.

  8. 탐색이 종료되면, cnt와 maxCnt를 비교하여 최댓값을 maxCnt에 저장하고, 초기위치의 값을 저장한다.(cnt > maxCnt일 경우)

  9. 만약 cnt == maxCnt일 경우, 초기위치의 두 값을 비교해서 더 작은 값을 저장한다.

  10. 저장한 maxCnt와 초기 위치의 값을 출력한다.

소스 코드


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

public class D4_1861_정사각형방 {  
	// 현재 위치

	public static void main(String[] args) throws NumberFormatException, IOException {

		System.setIn(new FileInputStream("input_1861.txt"));
		//				 우		좌	  하		상
		int[][] dir = { {0,1},{0,-1},{1,0},{-1,0} };

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


		int T = Integer.parseInt(in.readLine());

		for(int tc=1;tc<=T;tc++) {

			int x = 0;
			int y = 0;

			int N = Integer.parseInt(in.readLine());

			int[][] arr = new int[N][N];

			StringTokenizer st;

			// 2차원 배열 할당
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(in.readLine()," ");
				for(int j=0;j<N;j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			int maxCnt = 0;
			int answerarr = Integer.MAX_VALUE;
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++){
					int cnt = 0;
					x = i;
					y = j;
					while(true){
						int incnt = cnt;
						for(int d=0;d<4;d++) {
							int dx = x + dir[d][0];
							int dy = y + dir[d][1];
							if(dx >= 0 && dx < N && dy >= 0 && dy < N && arr[x][y]+1 == arr[dx][dy]) {
//								System.out.println(arr[x][y] +" : "+arr[dx][dy]);
								x = dx;
								y = dy;
								cnt++;
							}
						}
						if(cnt == incnt) {

							break;
						}
					}
					if(maxCnt < cnt) {
						maxCnt = cnt;
						answerarr = arr[i][j];
					}else if(maxCnt == cnt) {
						if(answerarr > arr[i][j]) {
							answerarr = arr[i][j];
						}
					}
				}
			}
			System.out.printf("#%d %d %d\n",tc,answerarr,++maxCnt);

		}

	}

}