SWEA D4 1861 정사각형방

SWEA D4 1861 정사각형방

 

 

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE#

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

SWEA_D4_1861_정사각형방 (naver.com)

SWEA_D4_1861_정사각형방

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d4;

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

/**
 * @author 은서파
 * @since 2020. 1. 28.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE#
 * @mem 30,084 kb
 * @time 229 ms
 * @caution
 *          #단순배열,
 *          [고려사항]
 *          한 방에서 연결되는 다른 방은 값의 차가 1이므로 있거나 없거나 둘 중의 하나이다.
 *          방에 대한 중복 방문이 발생할 수 있기 때문에 각 방에서 도달하는 회수를 저장해주자.
 *          [입력사항]
 *          [출력사항]
 */
public class SWEA_D4_1861_정사각형방 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;

	static int[][] deltas = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	static int T;
	static int N;
	static int[][] rooms;

	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		T = Integer.parseInt(input.readLine());
		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(input.readLine());
			rooms = new int[N][N];
			for (int r = 0; r < N; r++) {
				tokens = new StringTokenizer(input.readLine(), " ");
				for (int c = 0; c < N; c++) {
					rooms[r][c] = Integer.parseInt(tokens.nextToken());
				}
			}
			// 입력 완료
			//solve1(t);
			solve2(t);
			//solve3(t);
		}
		System.out.println(output);
	}

	//29,348 kb, 324 ms
	static void solve1(int t) {
		int maxStart = 0;
		int maxCnt = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				int sr = r;
				int sc = c;
				boolean canGo = true;
				int moveCnt = 1;
				int moveStart = rooms[sr][sc];
				while (canGo) {
					canGo = false;
					// 4방 탐색으로 가보기.
					for (int d = 0; d < deltas.length; d++) {
						int nr = sr + deltas[d][0];
						int nc = sc + deltas[d][1];
						if (isIn(nr, nc) && rooms[sr][sc] + 1 == rooms[nr][nc]) {
							moveCnt++;
							canGo = true;
							sr = nr;
							sc = nc;
							break;
						}
					}// 사방 탐색
				}// while
					// 여기까지 떨어진 것은 더이상 탐색할 곳이 없음
				if (moveCnt > maxCnt) {
					maxCnt = moveCnt;
					maxStart = moveStart;
				} else if (moveCnt == maxCnt) {
					maxStart = Math.min(moveStart, maxStart);
				}
			}
		}
		output.append(String.format("#%d %d %d %n", t, maxStart, maxCnt));
	}

	// 30,292 kb, 156 ms
	// 각 출발점 별로 도착점에 대한 정보를 모아놔 보자.
	static void solve2(int t) {
		// 각 출발점 번호를 index로 하는 배열(이동 거리 저장)
		int[] moved = new int[N * N + 1];
		int maxCnt = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				// 어떻든 이미 방문이 완료된 지점은 생략한다.
				if(moved[rooms[r][c]]==-1) {
					//System.out.println("스킵");
					continue;
				}
				int sr = r;
				int sc = c;
				boolean canGo = true;
				int moveCnt = 1;
				int moveStart = rooms[sr][sc];
				outer: while (canGo) {
					canGo = false;
					// 4방 탐색으로 가보기.
					for (int d = 0; d < deltas.length; d++) {
						int nr = sr + deltas[d][0];
						int nc = sc + deltas[d][1];
						if (isIn(nr, nc) && rooms[sr][sc] + 1 == rooms[nr][nc]) {
							// 이미 이동한 흔적이 있다면 거기에 추가해주자. 그리고 더이상 가볼 필요는 없다.
							if (moved[rooms[nr][nc]] != 0) {
								moveCnt += moved[rooms[nr][nc]];
								break outer;
							} else {
								// 중간에 거치는 지점은 사실 이제 관심 없다. 어쨋든 경우지일 경우는 moveStart에서의 이동 거리가 최대이므로 더이상 방문할 필요는 없다.
								moved[rooms[nr][nc]]=-1;
								moveCnt++;
								canGo = true;
								sr = nr;
								sc = nc;
								break;
							}
						}
					}// 사방 탐색
				}// while
				// 업데이트
				moved[moveStart] = moveCnt;
				maxCnt = Math.max(maxCnt, moveCnt);
			}
		}
		for (int i = 0; i < moved.length; i++) {
			if (moved[i] == maxCnt) {
				output.append(String.format("#%d %d %d %n", t, i, maxCnt));
				break;
			}
		}
	}

	//27,760 kb	144 ms
	static void solve3(int t) {
		int[] moved = new int[N * N + 1];
		int maxMoved = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				travelRecur(r, c, moved);
				maxMoved = Math.max(moved[rooms[r][c]], maxMoved);
			}
		}
		for (int i = 0; i < moved.length; i++) {
			if (moved[i] == maxMoved) {
				output.append(String.format("#%d %d %d %n", t, i, maxMoved));
				break;
			}
		}
	}

	// 명확한 의도는? 어떤 좌표에 들어갔을 때 이동 가능 회수를 반환한다.
	static int travelRecur(int r, int c, int[] moved) {
		// base part 1: - 이미 r, c에 대한 이동 경로가 잡혀있는 경우 
		if (moved[rooms[r][c]] > 0) {
			return moved[rooms[r][c]];
		}
		// 할일과 inductive part
		for (int d = 0; d < deltas.length; d++) {
			int nr = r + deltas[d][0];
			int nc = c + deltas[d][1];

			if (isIn(nr, nc) && rooms[nr][nc] == rooms[r][c] + 1) {
				return moved[rooms[r][c]] = 1 + travelRecur(nr, nc, moved);
			}
		}

		// base part 2: - 4방으로 탐색할 수가 없는 경우 
		return 1;
	}

	static boolean isIn(int r, int c) {
		return 0 <= r && r < N && 0 <= c && c < N;
	}

	static String src = "2\r\n" +
						"2\r\n" +
						"1 2\r\n" +
						"3 4\r\n" +
						"3\r\n" +
						"9 3 4\r\n" +
						"6 1 5\r\n" +
						"7 8 2";
}