[백준] 21922번 : 학부 연구생 민상 (C++)

21922번 : 학부 연구생 민상

---

문제)

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.

연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4$4$방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.

민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.

연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.

연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

 

 

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.

민상이가 원하는 자리는 몇 개 있는지 계산해주자.

 

 

입력 :

첫 번째 줄에는 연구실의 크기가 세로 N(1≤N≤2,000), 가로 M(1≤M≤2,000) 순으로 주어진다.

두 번째 줄부터 N + 1 줄까지 연구실 내부 구조 정보를 알려주는 값 M개가 주어진다.

 1,2,3,4는 위에서 설명한 물건의 종류이다.

 9는 에어컨을 의미하고, 0은 빈 공간을 의미한다.

에어컨은 0개 이상 50개 이하가 들어온다.

 

 

 

출력 :

민상이가 원하는 자리의 개수를 출력한다.

 

 

 

 

 

 

풀이)

바람의 방향, 물건의 종류에 따른 변화를 처리할 뾰족한 수가 떠오르지 않아 일일히 조건분기 처리해주었다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
vector<vector<int>> visited;
vector<pair<int, int>> air;
 
int total;
 
void dfs(int a, int b, int dict)
{
    // 연구실 밖으로 이탈했다면
    if (a < 0 || a >= n) return;
    if (b < 0 || b >= m) return;
 
    // 이미 체크한 자리라면
    if (!visited[a][b])
    {
        visited[a][b] = 1;
        total++;
    }
 
    if (vec[a][b] == 0)
    {
        if (dict == 0) dfs(a - 1, b, dict);
        else if (dict == 1) dfs(a + 1, b, dict);
        else if (dict == 2) dfs(a, b - 1, dict);
        else if (dict == 3) dfs(a, b + 1, dict);
    }
    else if (vec[a][b] != 0)
    {
        if (dict == 0)
        {    // 상
            if (vec[a][b] == 1) dfs(a - 1, b, dict);
            else if (vec[a][b] == 2) return;
            else if (vec[a][b] == 3) dfs(a, b + 1, 3);
            else if (vec[a][b] == 4) dfs(a, b - 1, 2);
        }
        else if (dict == 1)
        {    // 하
            if (vec[a][b] == 1) dfs(a + 1, b, dict);
            else if (vec[a][b] == 2) return;
            else if (vec[a][b] == 3) dfs(a, b - 1, 2);
            else if (vec[a][b] == 4) dfs(a, b + 1, 3);
        }
        else if (dict == 2)
        {    // 좌
            if (vec[a][b] == 1 || vec[a][b] == 9) return;
            else if (vec[a][b] == 2) dfs(a, b - 1, dict);
            else if (vec[a][b] == 3) dfs(a + 1, b, 1);
            else if (vec[a][b] == 4) dfs(a - 1, b, 0);
        }
        else if (dict == 3)
        {    // 우
            if (vec[a][b] == 1) return;
            else if (vec[a][b] == 2) dfs(a, b + 1, dict);
            else if (vec[a][b] == 3) dfs(a - 1, b, 0);
            else if (vec[a][b] == 4) dfs(a + 1, b, 1);
        }
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    vec.resize(n, vector<int>());
    visited.resize(n, vector<int>(m, 0));
        
    int temp;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> temp;
            vec[i].push_back(temp);
            if (temp == 9)
            {
                air.push_back(make_pair(i, j));
            }
        }
    }
 
    for (auto nxt : air)
    {
        if (visited[nxt.first][nxt.second] == 0)
        {
            visited[nxt.first][nxt.second] = 1;
            total++;
        }
 
        dfs(nxt.first - 1, nxt.second, 0);
        dfs(nxt.first + 1, nxt.second, 1);
        dfs(nxt.first, nxt.second - 1, 2);
        dfs(nxt.first, nxt.second + 1, 3);
    }
 
    cout << total;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/21922 

21922번: 학부 연구생 민상