C++에서 pair와 vector로 좌표 저장하기

pair 정의

first, second 라는 멤버변수를 가지는 클래스이며 두가지 값을 담아야 할 때 사용합니다. 

주로 이차원 배열의 인덱스 혹은 이차원 좌표 평면에서의 좌표를 저장하는데 사용됩니다.
정점 번호와 해당 정점 번호까지의 최단 거리를 묶어서 저장해야 하는 경우도 사용됩니다.

 

사용 예제

vector 객체에 pair 컨테이너를 통해 값 저장하는 방법

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

vector<pair<int, int>> vp1;
vector<pair<int, int>> vp2;

int main(){
    ios_base::sync_with_stdio(false);

    // make_pair를 통한 삽입 
    vp1.push_back(make_pair(2, 4));
   
    // 반복문을 통한 일반 삽입
    cin >> n;
    for(int i=0 ; i<n ; i++){
        vp2.push_back({i, j});
    }

    // vp1.first, vp1.second 사용하지 않고 값 끄집어 내기 
    int x, y;
    tie(x, y) = vp1;
    cout << x << " " << y << '\n';

    for(int i=0 ; i<n ; i++){
        cout << vp2[i].first << " " << vp2[i].second << '\n';
    }
    
    return 0;
}

 

문제 풀이

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

 

위 문제는 0 : {빈 칸}, 1 : {벽}, 2 : {바이러스} 로 이해하면
벽 3개를 세워 바이러스를 최대한 막고 빈 칸 최대 갯수를 구하는 문제입니다.
풀이 과정은 다음으로 정리할 수 있습니다.

1. 반복문을 통해 지도에서 벽 3개를 세우는 경우의 수 계산하기
2. DFS를 통해 각각의 벽을 세우는 경우의 수에서 바이러스가 퍼지는 좌표 변환하기
3. 반복문을 통해 방문 처리 되지 않은 나머지 빈 칸 갯수를 구하기 

 

vector<pair<int, int>>로 바이러스와 벽의 좌표 값을 따로 저장할 수 있습니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
int arr[9][9]; bool visited[9][9];
const int dy[4] = {1, 0, -1, 0};
const int dx[4] = {0, 1, 0, -1};
vector<pair<int, int>> virusList, wallList;
int n, m, ny, nx, ret;

void dfs(int y, int x){
    visited[y][x] = 1;
    for(int i=0 ; i<4 ; i++){
        ny = y + dy[i];
        nx = x + dx[i];
        // 범위 밖이거나 벽이거나 이미 방문한 곳인 경우 continue
        if(ny < 0 || nx < 0 || ny >= n || nx >= m || arr[ny][nx] == 1 || visited[ny][nx]) continue;
        dfs(ny, nx);
    }
}

int solve(){
    // 방문 배열 초기화
    fill(&visited[0][0], &visited[0][0] + 9*9, 0);
    // virus 위치 DFS
    for(auto it : virusList){
        dfs(it.first, it.second);
    }
    // 빈칸 개수 구하기
    int cnt = 0;
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<m ; j++){
            if(arr[i][j] == 0 && !visited[i][j]) cnt++;
        }
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<m ; j++){
            // 지도 값 입력
            cin >> arr[i][j];
            // 0일 때 빈 칸 좌표 vector 저장
            if(arr[i][j] == 0) wallList.push_back({i, j});
            // 2일 때 바이러스 좌표 vector 저장
            if(arr[i][j] == 2) virusList.push_back({i, j});
        }
    }
    // 1. 벽 3개 세울 경우의 수 (Brute Force)
    for(int i=0 ; i<wallList.size() ; i++){
        for(int j=0 ; j<i ; j++){
            for(int k=0 ; k<j ; k++){
                // 지도에 벽 3개 세우기
                arr[wallList[i].first][wallList[i].second] = 1;
                arr[wallList[j].first][wallList[j].second] = 1;
                arr[wallList[k].first][wallList[k].second] = 1;
                // 바이러스 구간 DFS & 빈칸 최대 영역 개수 구하기
                ret = max(ret, solve());
                // 지도에 벽 3개 다시 내리기 (why? 다음 경우의 수를 위해) 
                arr[wallList[i].first][wallList[i].second] = 0;
                arr[wallList[j].first][wallList[j].second] = 0;
                arr[wallList[k].first][wallList[k].second] = 0;
            }
        }
    }
    cout << ret << '\n';
    return 0;
}