swea 1861. 정사각형 방

[문제]

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

SW Expert Academy

[풀이]

bfs로 시도했다가 제한 시간 초과가 떴다.

dfs로 시도해보니 Pass할 수 있었다.

어차피 다음 방 번호가 현재 방 번호+1이어야 움직일 수 있다는 조건이 있으므로 중복되는 경로는 없다. visited배열 불필요.

 

#include <iostream>
//#include <queue>
using namespace std;
/*
struct Pos {
	int x, y;
};
*/

int T, N;
int Room[1001][1001];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int Max = -1;

/*
int bfs(int startx, int starty) {
	queue<Pos>q;
	q.push({ startx,starty });
	int cnt = 1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N )
				continue;
			if (Room[nx][ny] == Room[x][y] + 1) {
				cnt++;
				q.push({ nx,ny });
			}
		}
	}
	return cnt;
}
*/

int Cnt = 1;
void dfs(int x, int y) {
	for(int i=0;i<4;i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N)
			continue;
		if (Room[nx][ny] == Room[x][y] + 1) {
			Cnt++;
			dfs(nx, ny);
		}
	}
}

void solution() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N;
		Max = -1;
		int Rnum;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++){
				cin >> Room[i][j];
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				/*int ans = bfs(i, j);
				if (Max < ans) {
					Max = ans;
					Rnum = Room[i][j];
				}
				else if (Max == ans && Room[i][j]<Rnum) {
					Rnum = Room[i][j];
				}*/
				dfs(i, j);
				if (Max < Cnt) {
					Max = Cnt;
					Rnum = Room[i][j];
				}
				else if (Max == Cnt && Room[i][j] < Rnum)
					Rnum = Room[i][j];
				Cnt = 1;
			}
		}
		cout << '#' << t << ' ' << Rnum << ' ' << Max << '\n';
	}
}

int main() {
	solution();
	return 0;
}