[5650] 핀볼

풀이

1. 스택메모리가 1MB이다. 핀볼이 벽을 튕기도 돌아갈 때는 벽까지 온 경로를 그대로 따라감에 착안하여 벽을 만나는 순간 return 하게 해야한다.

코드

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

typedef struct {
	//웜홀 : 저장된 적이 없으면 -1
	int x1;
	int y1;
	int x2;
	int y2;
}holl;

int map[110][110];
holl h[11];
#define RIGHT 0
#define LEFT 1
#define DOWN 2
#define UP 3
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int sx = 0, sy = 0;
int dfs(int x, int y, int point, int dir, int len) {
	//시작 좌표로 시작해서
	int nx = x, ny = y;
	//한 칸 이동하고
	nx = nx + dx[dir];
	ny = ny + dy[dir];
	//이동한 좌표에 맞는 방향으로 고치기
	if (nx < 0 || nx >= len) { //맵 밖으로 나가는 경우 방향 바꾸기
		point *= 2;
		point += 1;
		return point;
		/*
		벽을 박으면 벽까지 오는 경로 그대로 다시 돌아가기 때문에 스텍 메모리를 줄이기 위함
		if (dir == DOWN) dir = UP;
		else dir = DOWN;
		dfs(nx, ny, point, dir, len);*/
	}
	else if (ny < 0 || ny >= len) { //맵 밖으로 나가는 경우 방향 바꾸기
		point *= 2;
		point += 1;
		return point;
		/*
		벽을 박으면 벽까지 오는 경로 그대로 다시 돌아가기 때문에 스텍 메모리를 줄이기 위함
		if (dir == RIGHT) dir = LEFT;
		else dir = RIGHT;
		dfs(nx, ny, point, dir, len);*/
	}
	else if (map[nx][ny] == -1) {
		return point;
	}
	else if (sx == nx && sy == ny) {
		return point;
	}
	else if (map[nx][ny] == 5) { //사각형 블럭
		point += 1;
		if (dir == RIGHT) dir = LEFT;
		else if (dir == LEFT) dir = RIGHT;
		else if (dir == UP) dir = DOWN;
		else if (dir == DOWN) dir = UP;
		dfs(nx, ny, point, dir, len);
	}
	else if (map[nx][ny] == 1) { //1 번 블럭
		point += 1;
		if (dir == RIGHT) dir = LEFT;
		else if (dir == LEFT) dir = UP;
		else if (dir == UP) dir = DOWN;
		else if (dir == DOWN) dir = RIGHT;
		dfs(nx, ny, point, dir, len);
	}
	else if (map[nx][ny] == 2) { //2 번 블럭
		point += 1;
		if (dir == RIGHT) dir = LEFT;
		else if (dir == LEFT) dir = DOWN;
		else if (dir == UP) dir = RIGHT;
		else if (dir == DOWN) dir = UP;
		dfs(nx, ny, point, dir, len);
	}
	else if (map[nx][ny] == 3) { //3 번 블럭
		point += 1;
		if (dir == RIGHT) dir = DOWN;
		else if (dir == LEFT) dir = RIGHT;
		else if (dir == UP) dir = LEFT;
		else if (dir == DOWN) dir = UP;
		dfs(nx, ny, point, dir, len);
	}
	else if (map[nx][ny] == 4) { //4 번 블럭
		point += 1;
		if (dir == RIGHT) dir = UP;
		else if (dir == LEFT) dir = RIGHT;
		else if (dir == UP) dir = DOWN;
		else if (dir == DOWN) dir = LEFT;
		dfs(nx, ny, point, dir, len);
	}
	else if (6 <= map[nx][ny] && map[nx][ny] <= 10) {
		int temp = map[nx][ny];
		if (h[temp].x1 == nx && h[temp].y1 == ny) {
			nx = h[temp].x2;
			ny = h[temp].y2;
		}
		else {
			nx = h[temp].x1;
			ny = h[temp].y1;
		}
		return dfs(nx, ny, point, dir, len);
	}
	else if (map[nx][ny] == 0) {
		dfs(nx, ny, point, dir, len);
	}else {
		cout << "ERROR " << map[x][y] << "\n";
	}
}

int main(void) {
	int tcase = 0;
	cin >> tcase;
	for (int tc = 1; tc <= tcase; tc++) {
		int len = 0; 
		cin >> len;
		//tc마다 초기화
		int ans = 0;
		memset(map, -1, sizeof(map));
		for (int i = 6; i <=10 ; i++) {
			h[i].x1 = -1;
			h[i].y1 = -1;
			h[i].x2 = -1;
			h[i].x2 = -1;
		}
		//맵 입력
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				cin >> map[i][j];
				if (6 <= map[i][j] && map[i][j] <= 10) {
					//웜홀 좌표 저장
					int temp = map[i][j];
					if (h[temp].x1 == -1 && h[temp].y1 == -1) {
						h[temp].x1 = i;
						h[temp].y1 = j;
					}
					else {
						h[temp].x2 = i;
						h[temp].y2 = j;
					}
				}
			}
		}
		//전체 맵을 돌면서 0인 위치에서 모든 방향으로의 dfs를 진행
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (map[i][j] == 0) {
					for (int dir = 0; dir < 4; dir++) {
						sx = i;
						sy = j;
						ans = max(ans, dfs(i, j, 0, dir, len));
					}
				}
			}
		}
		//dfs마다 결과값을 return 하고 ans 최대값을 출력
		cout << "#" << tc << " " << ans << "\n";
	}
	return 0;
}