2151. 거울설치

 
https://www.acmicpc.net/problem/2151

2151번: 거울 설치

 
 

 

 
 

Point

•  "#" ▶︎ 문
•  "!" ▶︎ 거울 설치 가능한 구역
•  "*" ▶︎ 벽
• 거울을 45도 기울어진 대각선으로 설치해야 한다.
• 문에서 문을 보기 위해 거울을 설치할 때, 설치해야 하는 거울의 최솟값을 구하는 문제.

 

다음과 같이 두 가지 방법이 있다.

 

테스트케이스 1번의 경우에는

테스트케이스 1번 그림

그림과 같이 거울을 설치하면 문에서 문을 볼 수 있다.
 

 

 

Point1 )

우선 거울과 문에 번호를 지정해주려한다. 
문의 시작번호와 끝번호를 따로 저장해두기만 하면 문과 거울 모두 하나의 벡터로 취급할 수 있다 ( 코드 참조 )
 

Point2)

 
dist[Start에서 갈 수 있는 거울번호]에 0값저장 , 갈 수 있는 번호들 push 
->  pop -> dist[pop한 거울번호에서 갈 수 있는 번호]에 +1 저장, 갈 수 있는 번호들 push 
로직을 반복하면서 BFS를 진행해주면 된다.
 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

int n;
vector<vector<char>> area(51,vector<char>(51));
vector<pair<int,int>> mirror;
vector<vector<int>> mirrorNum(51,vector<int>(51));
vector<vector<int>> doorNum(51,vector<int>(51));
vector<pair<int,int>> door;
int start=-1;
int dest=-1;

void bfs(int start,vector<int>&dist, vector<vector<bool>>&check)
{
    queue<int>q;
    q.push(start);
	
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        for(int i=0;i<mirror.size();i++)
        {	
        
        	// 현재 번호에서 i번호로 갈 수 있고, dist에 기록되지 않았다면 
            if(check[now][i] && dist[i]==-1)
            {   
                dist[i] = dist[now]+1;
                // cout << i << ' ' << dist[i] << endl;
                q.push(i);
            }
        }
    }
}
int main()
{
    FASTio;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> area[i][j];
			
            
            // 문인 경우 -> 시작점과 끝점만 기록한다면 거울과 동일하게 취급해도 됨.
            if(area[i][j]=='#')
            {	
            
            	// 시작번호 기록
                if(start==-1)
                {
                    start = mirror.size();
                }
                
                // 끝번호기록
                else
                {
                    dest = mirror.size();
                }
                mirror.push_back({i,j});
                
                // 좌표에 거울 번호 기록
                mirrorNum[i][j] = mirror.size()-1;
            }

            else if(area[i][j]=='!')
            {	
                mirror.push_back({i,j});
                
                // 좌표에 거울 번호 기록 
                mirrorNum[i][j] = mirror.size()-1;
            }
        }
    }


    vector<vector<bool>>check(mirror.size(),vector<bool>(mirror.size(),false));
	
    
    for(int i=0;i<mirror.size();i++)
    {
        for(int k=0;k<4;k++)
        {
        	// 거울 번호를 통해서 거울 좌표를 뽑아냄
            int ny = mirror[i].first + dy[k];
            int nx = mirror[i].second + dx[k];
            
            while(1)
            {	
            	// 영역 밖인경우 break
                if(!(ny>=0 && nx>=0 && nx<n && ny<n))
                {  
                    break;
                }
				
                // 벽을 만난 경우 break
                if(area[ny][nx]=='*')
                {
                    break;
                }
				
                // 거울이나 벽을 만난경우
                if(area[ny][nx]=='#' || area[ny][nx]=='!')
                {	
                	// i번에서 mirrorNum[ny][nx] 번째 거울로 갈 수 있음을 의미함
                    check[i][mirrorNum[ny][nx]] = true;
                    // cout << i << ' ' << mirrorNum[ny][nx] << endl;
                }
				
                // 조건 내에서
                // 위끝까지 살핌-> 아래끝까지살핌 -> 좌끝까지 살핌 -> 우 끝까지 살핌
                ny += dy[k];
                nx += dx[k];
            }
        }
    }
    
    vector<int> dist(mirror.size(),-1);

	
    bfs(start,dist,check);
    
    cout << dist[dest];


  
    return 0;
}

 

 
 
문제를 이해하는데 굉장히 오래걸렸다.. 문제 이해뿐만 아니라 거울을 45도로 설치한다는 점에서 거울을 어떻게 설치해야 되는지 아이디어도 안 떠올라서 난감했다. 강의를 보고 겨우 문제는 꾸역꾸역 이해했지만 풀이를 보고나서는 이런 아이디어를 어떻게 떠올리는지 감탄만 나왔다. 앞으로는 조금 더 고민하고 생각해보고 구현해보는 연습을 해야겠다..