[SWEA 5650] 핀볼 게임 (C++) (2가지 풀이)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo

SW Expert Academy

1. 주의할 점

- 매 TC마다 웜홀위치, Arr[][]배열을 초기화 해줘야 한다

- 벽을 전부 블록 5번이라고 생각하고 푼다

 

[BFS] -1683ms

2. 구현

- 매 X,Y값마다 Arr[Y][X]==1이면 BFS를 시작하며 , Check[][] 배열을 모두 False로 초기화 하고 시작한다

- Queue에 시작 Y,X를 기준으로 4방향을 모두 넣고 시작한다

- Queue에서 원소 1개씩 빼며 현 위치가 블랙홀, 이미 방문한 위치, 시작점(첫 시작의 경우 제외)라면 Result를 갱신하고 Continue수행

- 위의 경우가 아니라면 Check[][][] 값을 갱신시키고, 다음 칸의 위치를 구한다

- 다음 칸이 0이나 블랙홀이라면 우선 큐에 추가, 블록이라면 방향바꿔주고, 값도 바꿔서 큐에 넣는다. 그리고 웜홀이라면 위치를 바꿔서 큐에 넣는다

- 위의 과정들을 계속 반복한다

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
struct info {
	int x, y, val, dir;
	bool s;		//시작지점인지 검사
};
info tmp;
int arr[102][102];
bool check[102][102][4];
int hx1[11], hx2[11], hy1[11], hy2[11];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int dir[6][4] = { {0,0,0,0},{2,3,1,0},{1,3,0,2},{3,2,0,1},{2,0,3,1},{2,3,0,1} };
int num, result, sx, sy;

void bfs(int y, int x) {
	queue<info> q;
	for (int i = 0; i < 4; i++) {
		tmp.x = x;
		tmp.y = y;
		tmp.dir = i;
		tmp.val = 0;
		tmp.s = true;
		q.push(tmp);
	}
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cv = q.front().val;
		int cd = q.front().dir;
		bool cs = q.front().s;		
		q.pop();
		if (arr[cy][cx] == -1 || (sx == cx && sy == cy && !cs) || check[cy][cx][cd]) {		//시작지점으로 돌아오거나 블랙홀에 빠진 경우
			result = max(result, cv);
			continue;
		}
		check[cy][cx][cd] = true;
		int nd = cd;
		int nx = cx + dx[cd];
		int ny = cy + dy[cd];
		int v = arr[ny][nx];	
		tmp.x = nx;
		tmp.y = ny;
		tmp.dir = cd;
		tmp.val = cv;
		tmp.s = false;
		if (v < 1) 	q.push(tmp);		
		else if (v < 6) {
			tmp.dir = dir[v][cd];
			tmp.val = cv + 1;
			q.push(tmp);
		}
		else if(v>5){
			if (nx == hx1[v] && ny == hy1[v]) {
				tmp.x = hx2[v];
				tmp.y = hy2[v];
			}
			else {
				tmp.x = hx1[v];
				tmp.y = hy1[v];
			}
			q.push(tmp);
		}
	}	
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		result = 0;
		cin >> num;
		for (int i = 5; i < 11; i++) {
			hx1[i] = -1, hy1[i] = -1;
			hx2[i] = -1, hy2[i] = -1;
		}
		for (int i = 0; i < num+2; i++) 
			for (int j = 0; j < num+2; j++) {
				if (i == 0 || j == 0 || i == num + 1 || j == num + 1) {
					arr[i][j] = 5;
					continue;
				}
				cin >> arr[i][j];
				if (arr[i][j] > 5) {
					int v = arr[i][j];
					if (hx1[v] == -1) {
						hx1[v] = j; hy1[v] = i;
					}
					else {
						hx2[v] = j; hy2[v] = i;
					}
				}
			}
		for (int i = 1; i <= num; i++)
			for (int j = 1; j <= num; j++) {
				if (arr[i][j] == 0) {
					memset(check, false, sizeof(check));
					sx = j;
					sy = i;
					bfs(i, j);
				}
			}		
		cout << "#" << t << " " << result << '\n';		
	}
	system("pause");
	return 0;
}

 

[DFS] - 49ms

 

2. 구현 (BFS와 비교하여 추가된 조건)

- Block중에서 부딪혔을때 정확히 반대방향으로 보내는 블록 + 방향일 경우, -1로 설정해둔다 (해당 블록에 닿기까지 닿은 블록/벽 *2 + 1(현재 닿은 벽)으로 계산하기 위해)

- 웜홀에 의해 무한루프가 돌지 않도록 조건을 설정한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
    int x, y;
};
info tmp;
int arr[102][102], num, result;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int block[6][4] = { {0,0,0,0}, {-1,-1,1,0},{1,-1,-1,2},{3,2,-1,-1},{-1,0,3,-1},{-1,-1,-1,-1} };
vector<info> warmhole[11];
 
void dfs(int y, int x, int dir) {
    int nx = x, ny = y, nd = dir, val = 0;
    while (1) {
        nx += dx[nd];
        ny += dy[nd];
        int v = arr[ny][nx];
        if (v== 0 && val == 0) break;       //웜홀에 의한 무한루프
        if ((nx==x && ny==y)|| v == -1) {       //종료조건
            result = max(result, val);
            break;
        }
        if (0 < v && v < 6) {     //블록
            nd = block[v][nd];
            if (nd == -1) {
                result = max(result, val * 2 + 1);
                break;
            }
            else
                val++;
        }
        else if (v > 5) {        //웜홀
            if (nx == warmhole[v][0].x && ny == warmhole[v][0].y) {
                nx = warmhole[v][1].x;
                ny = warmhole[v][1].y;
            }
            else {
                nx = warmhole[v][0].x;
                ny = warmhole[v][0].y;
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int test;
    cin >> test;
    for (int t = 1; t <= test; t++) {
        cin >> num;
        //초기화
        for (int i = 0; i < num + 2; i++) {      //외곽을 벽5랑 같게 세팅
            arr[0][i] = 5;
            arr[i][0] = 5;
            arr[num + 1][i] = 5;
            arr[i][num + 1] = 5;
        }
        for (int i = 6; i < 11; i++)
            warmhole[i].clear();
        result = 0;
 
        for (int i = 1; i <= num; i++) 
            for (int j = 1; j <= num; j++) {
                cin >> arr[i][j];
                if (arr[i][j] > 5) {
                    tmp.x = j;
                    tmp.y = i;
                    warmhole[arr[i][j]].push_back(tmp);
                }
            }
        for (int i = 1; i <= num; i++) 
            for (int j = 1; j <= num; j++) {
                if (arr[i][j] == 0) {
                    for (int k = 0; k < 4; k++)
                        dfs(i, j, k);
                }
            }       
        cout << "#" << t << " " << result << '\n';
    }
    return 0;
}