[Algorithm][C++] SWEA 4340. [연습문제] 파이프 연결

url: https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

풀이 핵심

1. 완전 탐색 문제

 

2. 제한 시간 초과를 피하기 위해 cache[50][50][4] 배열을 만들어 두는 것이 필요하다. MAXN (50) * MAXN + 1 로 cache 배열을 초기화 하고 최초 방문일 경우 현재 r, c (행, 열), dir (방향)인 cache[r][c][dir]에 현재까지의 파이프 길이를 저장한다. 중복 방문 했을 경우 현재의 길이가 저장 된 길이보다 크다면 return 하는 방식으로 가지치지 한다.

 

3. 1, 2 타입의 파이프는 같은 종류 파이프로 생각하면 된다. 그리고 3, 4, 5, 6 파이프는 모두 같은 파이프라고 생각한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAXN	50

int T, N, ans;
int map[MAXN][MAXN];
bool visit[MAXN][MAXN];
int cache[MAXN][MAXN][4];
const int temp_max = MAXN * MAXN + 1;
int er, ec;

void solve(const int r, const int c, const int dir, const int length) {
	if (r == er && c == ec) {
		if (ans > length) {
			ans = length;
		}
		return;
	}
	if (r < 0 || r >= N || c < 0 || c >= N || visit[r][c] || map[r][c] == 0) return;
	if (visit[r][c] || map[r][c] == 0) return;
	if (cache[r][c][dir] < length) return;
	visit[r][c] = true;
	cache[r][c][dir] = length;
	const int type = map[r][c];
	// dir 0: Up, 1: Right, 2: Down, 3: Left
	if (type <= 2) {
		if (dir == 0) {
			solve(r - 1, c, dir, length + 1);
		}
		else if (dir == 1) {
			solve(r, c + 1, dir, length + 1);
		}
		else if (dir == 2) {
			solve(r + 1, c, dir, length + 1);
		}
		else {
			solve(r, c - 1, dir, length + 1);
		}
	}
	else {
		if (dir == 0 || dir == 2) {
			solve(r, c + 1, 1, length + 1);
			solve(r, c - 1, 3, length + 1);
		}
		else if (dir == 1 || dir == 3) {
			solve(r + 1, c, 2, length + 1);
			solve(r - 1, c, 0, length + 1);
		}
	}
	visit[r][c] = false;
}

int main() {
	// freopen("input.txt", "r", stdin);
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		ans = temp_max;
		scanf("%d", &N);
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				scanf("%d", &map[r][c]);
				visit[r][c] = false;
				for (int dir = 0; dir < 4; dir++) {
					cache[r][c][dir] = temp_max;
				}
			}
		}
		er = N - 1, ec = N;
		solve(0, 0, 1, 0);
		for (int r = 0; r < N; r++)for (int c = 0; c < N; c++) for (int dir = 0; dir < 4; dir++)cache[r][c][dir] = temp_max;
		er = 0, ec = -1;
		solve(N - 1, N - 1, 3, 0);
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}