[SWEA1861] 정사각형 방

[SWEA1861] 정사각형 방

SWEA 1861 정사각형 방 - 로그인이 필요합니다.

문제 설명

• N*N 배열의 각 방은 1~N^2 의 번호가 붙어있다.

• 하나의 방에서 상하좌우 로 움직일 수 있다.

• 이동할 때는 현재 방번호보다 딱 1만큼 큰 방으로만 움직일 수 있다.

• 가장 많이 움직일 때의 이동한 방의 개수와 그럴때의 시작 방의 번호를 출력하면 된다.

접근방법

• 먼저 배열을 입력받을때, 구조체로 x좌표와 y좌표가 저장된 새로운 배열을 하나 만들어서 그 배열의 인덱스엔 방번호, 그리고 그 배열값으로 배열의 x좌표 y좌표를 적어주는 전처리 과정 을 한다.

• 위의 전처리를 하는 이유는 한번 방이동을 한 후 다음 번호를 찾기위한 시간을 줄이기 위한 이유이다. 전처리를 해두면, 인덱스 번호로 바로 방번호를 참조할 수 있으므로 상수시간에 방에 들어있는 번호를 찾을 수 있다.

• 방번호가 1인곳부터 시작하여 DFS를 한다. 더이상 DFS를 진행할 수 없을 경우 방번호와 이동한 방의 개수를 저장한다.

• 그 다음 탐색할 방은 그 전단계에서 DFS로 탐색을 하여 도착한 마지막 방번호 +1 을 시작할 방 으로 정하면 된다.

• 첫번째 탐색이 1번방~ 10번방까지 갔을 경우, 11번방부터 새로 탐색을 하는 것이다. 2번방부터 조사하지 않는 이유는 2번방역시 10번방까지 가고 더이상 탐색을 못할 것이기때문에 1번방~10번방까지 탐색한 방의 개수가 무조건 더 클것이기 때문이다.

코드리뷰

• 최대한 실행시간을 줄이는데 초점을 맞추고 풀어보았다.

• D4문제라기엔 난이도가 쉬운 편.

• 오랜만에 문제풀어서 재밌었다..

#include <iostream>
using namespace std;

int N;
int board[1005][1005];
int check[1005][1005];
int tmp_num, tmp_result;
int dc[4] = { 0,0,-1,1 };
int dr[4] = { -1,1,0,0 };

typedef struct {
	int x;
	int y;
}pre_process;

typedef struct {
	int start_pos;
	int end_pos;
	int maxnum;
}MAX;

pre_process pre_board[1000005];
MAX result;

void dfs(int start) {
	int xnow = pre_board[start].x;
	int ynow = pre_board[start].y;
	tmp_result += 1;
	result.end_pos = start;
	check[xnow][ynow] = 1;
	for (int k = 0; k < 4; k++) {
		int xnext = xnow + dc[k];
		int ynext = ynow + dr[k];
		if (xnext < 0 || xnext >= N || ynext < 0 || ynext >= N || check[xnext][ynext] == 1 || board[xnext][ynext] != board[xnow][ynow] + 1)
			continue;
		dfs(start+1);
		check[xnext][ynext] = 0;
		return;
	}
}

int main() {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		scanf("%d", &N);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%d", &board[i][j]);
				pre_board[board[i][j]].x = i;
				pre_board[board[i][j]].y = j;
			}
		}
		int start = 1;
		while (start <= N * N) {
			tmp_num = start;
			dfs(start);
			check[pre_board[start].x][pre_board[start].y] = 0;
			if (tmp_result > result.maxnum) {
				result.start_pos = tmp_num;
				result.maxnum = tmp_result;
			}
			tmp_result = 0;
			start = result.end_pos + 1;
		}
		printf("#%d %d %d\n", t, result.start_pos, result.maxnum);
		result.start_pos = 0;
		result.end_pos = 0;
		result.maxnum = 0;
	}
	return 0;
}