[C++] SWEA 1861 - 정사각형 방

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE

SW Expert Academy

<풀이>

1. 방 정보를 입력받는다.

2. 방을 최대로 이동할 수 있을 때의 방 숫자와, 그 때 이동한 방 개수를 출력한다.

 

<해법>

1. 이동한 방 개수를 구하는 방법

=> 이동한 방 개수를 구하는 방법은 굉장히 간단합니다. 각 좌표마다 방을 이동할 수 있을때까지 이동하고, 총 개수를 구합니다. 하지만 여기서 조금 더 생각하면 중복을 제거할 수 있는 원리가 보입니다.

위 그림과 같이 4번 방에서 이동할 수 있는 방의 개수는 (1+3번 방에서 이동할 수 있는 방의 개수) 입니다.

따라서, 위 점화식을 사용하여 DP로 접근하면 중복을 제거할 수 있습니다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
//구조체 : 좌표
struct pos {
    int x, y;
};
 
//4방향 : 북, 동, 남, 서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int map[1000][1000];
int cache[1000][1000]; //DP 저장 배열
int N;
int Answer_RoomNum;
int Answer_RoomCnt;
 
//현재 좌표가 범위 안에 있는지 판단
bool isInner(pos p) {
    if (p.x < 0 || p.y < 0 || p.x >= N || p.y >= N) {
        return false;
    }
    return true;
}
 
//현재 좌표에서 다음 좌표로 이동할 수 있는지 판단
bool canGo(pos cur, pos nxt) {
    if (map[cur.x][cur.y] + 1 == map[nxt.x][nxt.y]) {
        return true;
    }
    return false;
}
 
//DP 풀이
int move(pos cur) {
 
    int& ret = cache[cur.x][cur.y];
 
    if (ret != -1) {
        return ret;
    }
 
    ret = 1;
 
    for (int i = 0; i < 4; i++) {
        pos nxt = cur;
        nxt.x += di[i];
        nxt.y += dj[i];
 
        if (!isInner(nxt)) {
            continue;
        }
 
        if (canGo(cur, nxt)) {
 
            /*
            현재 좌표에서 이동할 수 있는 방의 수 = 1 + 다음 좌표에서 이동할 수 있는 방의 수
            */
            ret += move(nxt);
        }
    }
 
    return ret;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        memset(cache, -1, sizeof(cache));
        N = 0;
        Answer_RoomNum = 0, Answer_RoomCnt = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
 
                //{i, j}에서 이동할 수 있는 방의 개수 구하기
                int Tmp_RoomCnt = move({ i, j });
 
                //결과 갱신
                if (Tmp_RoomCnt > Answer_RoomCnt) {
                    Answer_RoomCnt = Tmp_RoomCnt;
                    Answer_RoomNum = map[i][j];
                }
                else if (Tmp_RoomCnt == Answer_RoomCnt) {
                    Answer_RoomNum = min(Answer_RoomNum, map[i][j]);
                }
            }
        }
 
        //결과 출력
        cout << "#" << test_case << " " << Answer_RoomNum << " " << Answer_RoomCnt << "\n";
    }
 
    //종료
    return 0;
}

 

DP에 대해 알아볼 수 있는 문제였습니다.