29. SW_Test 연습 백준 2151번 거울 설치

문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

입력

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

출력

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

 

쉬운문제인줄 알고 백트래킹기법으로 풀었다가 시간 초과 떠서 3시간 날린문제..

해답방법은 BFS 기법으로 푸는 문제이다.

해결 순서는 다음과 같다.

1. 입력받으면서 시작점과 , 끝나는 지점을 구분한다. (추후 중복방지를 위해)

2. 3차원 배열 vist 를 이용하여 각 방향으로 이동하였을때 최소 거울 사용횟수를 입력해나가며 진행한다.

3. 즉, vist배열의 의미는  vist[y][x][d] = "d 방향으로 이동할때 최소 거울 수 " 라고 볼수있다.

4. 최종목적지에 도달하면 최소거울수를 업데이트한다.

5. 정답 출력

 

#pragma warning (disable :4996)
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct point {
	int y, x, d;
};
queue <point> q;
char Map[51][51];
int N ,fy,fx;
int ans = 999999;
int vist[51][51][4];
int dir[4][2] = { {-1,0} ,{1,0}, {0,-1}, {0,1} };
void move() {
	while (!q.empty()){
		int cunY = q.front().y;
		int cunX = q.front().x;
		int cund = q.front().d;
		q.pop();
		int nextY = cunY + dir[cund][0];
		int nextX = cunX + dir[cund][1];
		if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N) continue;
		if ( Map[nextY][nextX] == '*') continue;
		if (Map[nextY][nextX] == '.') {
			if (vist[nextY][nextX][cund] > vist[cunY][cunX][cund]) {
				vist[nextY][nextX][cund] = vist[cunY][cunX][cund];
				point p;
				p.y = nextY;
				p.x = nextX;
				p.d = cund;
				q.push(p);
			}
		}
		if (Map[nextY][nextX] == '!') {
			
			if (vist[nextY][nextX][cund] > vist[cunY][cunX][cund]) {
				vist[nextY][nextX][cund] = vist[cunY][cunX][cund];
				point p;
				p.y = nextY;
				p.x = nextX;
				p.d = cund;
				q.push(p);
			}
			if (cund == 0 || cund ==1 ) {
				if (vist[nextY][nextX][2] > vist[cunY][cunX][cund] + 1) {
					vist[nextY][nextX][2] = vist[cunY][cunX][cund] + 1;
					point p;
					p.y = nextY;
					p.x = nextX;
					p.d = 2;
					q.push(p);
				}
				if (vist[nextY][nextX][3] > vist[cunY][cunX][cund] + 1) {
					vist[nextY][nextX][3] = vist[cunY][cunX][cund] + 1;
					point p;
					p.y = nextY;
					p.x = nextX;
					p.d = 3;
					q.push(p);
				}
			}
			else {
				if (vist[nextY][nextX][0] > vist[cunY][cunX][cund] + 1) {
					vist[nextY][nextX][0] = vist[cunY][cunX][cund] + 1;
					point p;
					p.y = nextY;
					p.x = nextX;
					p.d = 0;
					q.push(p);
				}
				if (vist[nextY][nextX][1] > vist[cunY][cunX][cund] + 1) {
					vist[nextY][nextX][1] = vist[cunY][cunX][cund] + 1;
					point p;
					p.y = nextY;
					p.x = nextX;
					p.d = 1;
					q.push(p);
				}
			}
		}
		if (Map[nextY][nextX] == '#'&& fy == nextY && fx == nextX) {
			vist[nextY][nextX][cund] = vist[cunY][cunX][cund];
			ans = min(ans, vist[nextY][nextX][cund]);
		}
	}
}
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d",&N );
	for (int i = 0; i < N;i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1s", &Map[i][j]);
			for (int d = 0; d < 4; d++) {
				vist[i][j][d] = 999999;
			}
			if (Map[i][j] == '#') {
				if (q.empty()) {
					for (int d = 0; d < 4; d++) {
						point p;
						p.y = i;
						p.x = j;
						p.d = d;
						q.push(p);
						vist[i][j][d] = 0;
					}
				}
				else {
					fy = i;
					fx = j;
				}
			}
		}
	}
	move();
	printf("%d", ans);
	return 0;
}