[2021 ICT 하반기] 3번 문제

문제요약: 어떤 2차원 grid가 주어지고 각 셀은 벽 또는 빈 공간이고, 각 셀을 동서남북으로 이동할 수 있고 한칸을 이동하는데 걸리는 시간은 1입니다. 시작점 left-top에서 도착점 right-bottom까지 이동하는 시간이 문제에서 주어지는 maxTime 이하이면 Yes를 리턴하고 아니면 No를 리턴하는 문제입니다.

 

요약: 출발지점부터 도착지점까지 너비우선탐색(BFS)를 돌려서 도착지점까지의 최단거리를 구합니다. 그리고 도착지점까지의 최단거리가 문제에서 주어진 maxTime초과이거나 혹은 벽에 막혀서 도착지점까지 도착하지 못하는경우 No를 리턴하고 아닌 경우 다 Yes로 리턴합니다.

 

*BFS: 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이고 큐를 사용한다.

3번 문제

#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨

/*
   문제:
      어떤 grid(2차원 맵이겠죠)가 주어지고, 각 cell은 '#' 또는 '.'이다. ('#'이면 벽이고, '.'이면 빈 공간이라고 생각하면 됨)
      각 cell을 동서남북으로 이동할 수 있고, 한 칸을 이동하는 데 걸리는 시간은 1이다.
      이 때, 시작점(left top)에서 도착점(right bottom)까지 이동하는 시간이 (문제에서 주어지는 maxTime) 이하이면 Yes를 리턴하고 아니면 No를 리턴하라.
         (주의: 모든 cell을 탐색했는데도, 벽('#')에 막혀서 도착점에 도달하지 못할 수도 있음)
*/
string reachTheEnd(vector<string> grid, int maxTime) {
   // 높이 height와 너비 width를 저장한다. 
   // height는 vector의 크기이고, width는 vector의 첫번째 원소(스트링)의 길이를 의미
   int height = grid.size(), width = grid[0].size(); 
   
   // 탐색 시, 동서남북으로 이동하기 위해 미리 세팅해둔 배열
   int dirx[4] = {0, 0, 1, -1}; 
   int diry[4] = {1, -1, 0, 0}; 

   // dist[i][j] 정의: 시작점 (0,0)에서 현재 좌표 (i,j)까지의 최단 거리를 저장
   // dist 벡터는 2차원 벡터로서, 원본 맵 grid와 같은 크기(height * width)를 갖는다. (예제 데이터대로면 3*4)
   // 높이는 height이고, 너비는 width인데, 모든 원소의 값을 -1로 초기화한다.
   // -1의 의미: 아직까지 도달하지 못했음을 의미. 만약 -1이 아니라면 이미 도착했다는 것이다.
   vector<vector<int> > dist(height, vector<int>(width, -1)); 
   dist[0][0] = 0; //시작점 (0,0)은 거리가 당연히 0이다. 시작점에서 시작점까지니까

   /*
      BFS(너비우선탐색)을 위해 큐를 선언하는데, 큐에 들어가는 각 원소는 pair 타입이다. (왜냐면 좌표를 저장해야하므로)
      pair는 STL에 내장된 구조체이다.
   */
   queue<pair<int, int> > q;
   q.push({0, 0}); //큐에다가 좌표(0, 0)을 넣는다. (BFS 탐색의 시작 위치가 (0,0)이라는 의미)
   while (!q.empty()) { // 큐가 비어있지않는 동안
      pair<int, int> cur = q.front(); // q에서 맨 앞에 있는 놈(좌표)를 꺼내서 cur라는 pair 타입 변수에 대입
      q.pop(); // cur에 저장했으니 q에서 맨 앞에 있는 놈을 삭제한다.
      for (int i=0; i<4; i++) { // 동서남북 4가지
         /*
            현재 좌표 (cur.first, cur.second)에다가 (+dirx[i], +diry[i])를 해서 next 좌표를 구한다.
            (+0, +1)하면 동쪽
            (+0, -1)하면 서쪽
            (+1, +0)하면 남쪽
            (-1, +0)하면 북쪽
         */
         pair<int, int> next = { cur.first + dirx[i], cur.second + diry[i] }; 

         // next 좌표(동서남북 중 하나)가 grid 밖으로 벗어나는 경우는 continue해서 스킵한다.
         if (next.first < 0 || next.first >= height || next.second < 0 || next.second >= width) continue;

         // next 좌표(동서남북 중 하나)가 원본 맵(grid)에서 벽인 경우('#'으로 표시된 경우) continue해서 스킵한다. (벽이니까 이동할 수 없음)
         if (grid[next.first][next.second] == '#') continue;

         // dist[next.first][next.second]가 -1이면(즉, 이때까지 한번도 next 좌표에 도달하지 못한 경우에만)
         if (dist[next.first][next.second] == -1) {

            // next 좌표의 distance 값을 갱신한다. (cur 좌표에서 1칸 움직인 것이므로, dist[cur.first][cur.second] + 1 값을 대입한다.)
            dist[next.first][next.second] = dist[cur.first][cur.second] + 1;

            // 큐에 next 좌표를 푸시한다.
            q.push(next);
         }
      }
   }

   /*
      도착점의 좌표는 (height-1, width-1)이다. (왜냐하면, 시작점이 (0,0)이기 때문에 도착점은 (height,width)가 아니라 -1씩 해줘야한다. 예를 들어 길이가 4인 배열은 인덱스가 0,1,2,3임)
      만약, 도착점의 distance가 -1이면 "No"를 리턴한다. (즉, 모든 cell을 탐색했는데도, 벽('#')에 막혀서 도착점에 도달하지 못한 경우) 
      또는 distance가 -1은 아니지만 maxTime보다 크다면 "No"를 리턴한다. (즉, 문제에서 주어진 시간 안에 도착하지 못한 경우)
      그 외의 경우는 모두 "Yes"
   */
   if (dist[height-1][width-1] == -1 || dist[height-1][width-1] > maxTime) return "No";
   return "Yes";
}

int main()
{
   // 입력하는 부분 생략하고, 바로 변수에 저장
   int n = 3; // size of grid[] rows
   vector<string> grid = { "..##", "#.##", "#..." }; //각 element의 타입이 string인 1차원 벡터 grid를 선언한다. 크기는 n이다. (n은 row 갯수=높이를 의미)
   int maxTime = 5; // maxTime
   
   // reachTheEnd 함수 호출 후 결과값 저장
   string answer = reachTheEnd(grid, maxTime);
   
   // 결과값 출력
   cout << answer;

   return 0; //정상 종료됨을 의미하는 return 0
}

 

 

 

 

주석 제거용

#include <bits/stdc++.h> 
using namespace std; 

string reachTheEnd(vector<string> grid, int maxTime) {
   int height = grid.size(), width = grid[0].size(); 

   int dirx[4] = {0, 0, 1, -1}; 
   int diry[4] = {1, -1, 0, 0}; 

   vector<vector<int> > dist(height, vector<int>(width, -1)); 
   dist[0][0] = 0; 

   queue<pair<int, int> > q;
   q.push({0, 0}); 
   while (!q.empty()) { 
      pair<int, int> cur = q.front();
      q.pop(); 
      for (int i=0; i<4; i++) { 
         pair<int, int> next = { cur.first + dirx[i], cur.second + diry[i] }; 
         if (next.first < 0 || next.first >= height || next.second < 0 || next.second >= width) continue;
         if (grid[next.first][next.second] == '#') continue;
         if (dist[next.first][next.second] == -1) {
            dist[next.first][next.second] = dist[cur.first][cur.second] + 1;

            q.push(next);
         }
      }
   }

   if (dist[height-1][width-1] == -1 || dist[height-1][width-1] > maxTime) return "No";
   return "Yes";
}

int main()
{

   int n = 3; 
   vector<string> grid = { "..##", "#.##", "#..." }; 
   int maxTime = 5; 
   
   string answer = reachTheEnd(grid, maxTime);
   
   cout << answer;

   return 0;
}