[SWA] 1861. 정사각형 방

1861. 정사각형 방

NxN 개의 방이 주어지고, 각각의 방은 1부터 n^2 사이의 모두 다른 숫자를 가지고 있다.

어떤 방에서 상하좌우로 방을 이동할 수 있는데, 이동할 방이 현재 방 번호보다 정확히 1만큼 더 커야만 이동이 가능하다.

위 상황에서 움직일 수 있는 최대 방 수와 시작 방 번호를 구하는 문제이다.

문제 해결 전략

만약 2->3->4로 이동할 수 있다고 생각해 보자.

2를 시작점으로 탐색할 경우 3과 4에 대해서는 탐색할 필요가 없게 된다.

2를 시작점으로 했을 때 3과 4를 거쳤고, 3을 시작점으로 해도 4를 거치게 되는데 어찌되든 2를 시작점으로 했을 때 움직일 수 있는 방이 최대가 되기 때문이다.

위의 아이디어로 주어진 방 번호를 1부터 오름차순으로 탐색을 시작하는데, 탐색 과정에서 거쳐갔던 방 번호들은 건너 뛰면 된다.

1번부터 차례로 배열에서 찾아내기 위해서는 O(n^2)의 시간복잡도가 걸리므로 vector에 저장 후 sort()를 통해 O(nlogn)으로 시간복잡도를 줄인다.

그리고 차례로 dfs를 적용하여 가장 깊이가 긴 것을 찾아내면 된다.

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
int arr[1001][1001];
int visited[1001][1001];
int xpos[4] = {-1,1,0,0};
int ypos[4] = {0,0,-1,1};
int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
     
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        int n;
        cin >> n;
        vector<pair<int,pair<int,int>>>v;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin >> arr[i][j];
                v.push_back(make_pair(arr[i][j],make_pair(i,j)));
            }
        }
        sort(v.begin(),v.end());
         
        int max = 0;
        int mx;
        for(int i=0;i<v.size();i++){
            if(visited[v[i].second.first][v[i].second.second] != 0)
                continue;
            queue<pair<pair<int,int>,int>>q;
            q.push(make_pair(make_pair(v[i].second.first,v[i].second.second),v[i].first));
            int cnt = 0;
            while(!q.empty())
            {
                int x,y,r;
                x = q.front().first.first;
                y = q.front().first.second;
                r = q.front().second;
                q.pop();
                if(visited[x][y] != 0)
                    continue;
                cnt++;
                visited[x][y] = 1;
                for(int j=0;j<4;j++)
                {
                    int nx = x + xpos[j];
                    int ny = y + ypos[j];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= n)
                        continue;
                    if(arr[nx][ny] == r+1)
                    {
                        q.push(make_pair(make_pair(nx,ny),r+1));       
                        break;
                    }                   
                }    
            }
            if(max < cnt)
            {
                max = cnt;
                mx = v[i].first;
            }
        }
         
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                arr[i][j] = 0;
                visited[i][j] = 0;
            }
        }
        cout << "#" << test_case << " " << mx << " " << max << "\n";
    }
    return 0;
}

생각해 볼 점

DP를 활용하여 문제를 풀 수 있다.

탐색하는 과정에서 특정 점에 대하여 이미 구해진 특정 점에서의 최댓값 과 탐색하는 과정에서 구해진 특정 점에 대한 값을 비교하여 최대값을 갱신해 주면 된다.

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc