금고 (SAFE) ( BOJ 14932 )

문제

14932. 금고 (SAFE) : https://www.acmicpc.net/problem/14932

14932번: 금고 (SAFE)

 

문제 파악하기

• N*N 행렬로 금고가 주어집니다. 금고는 버튼으로 구성되어 있으며, 모든 버튼을 누를 수 있는 위치를 찾아야 합니다.
• 모든 버튼은 항상 하나의 버튼만을 가리킵니다. 따라서 버튼 사이의 관계를 그래프로 나타낼 수 있습니다.
• 출력되는 결과는 총 3가지 입니다. 좌표를 출력하거나, "THIEF LOVE IT!"을 출력하거나 "TOO SAFE"를 출력해야 합니다.

 

문제 해결하기

• 문제를 해결하기 위해서는 버튼 사이의 관계를 방향 그래프로 나타내야 합니다.
  >> 현재 버튼에서 다음 버튼 사이에 간선을 추가해서 그래프를 만들어야 합니다.
• 어느 한 버튼에서 시작해서 모든 버튼을 누르기 위해서는 시작 버튼은 어떤 버튼도 접근할 수 없음을 의미합니다.
  >> 방향 그래프로 나타냈을 때, 진입 차수가 0인 버튼이 곧 시작 버튼이라고 할 수 있습니다.
• 따라서 진입 차수가 0인 버튼이 1개 있으면 해당 좌표를 출력하면 됩니다.
• 하지만 진입 차수가 0개인 버튼이 1개 이상인 경우에는 한번에 모든 버튼을 누를 수 없음을 의미합니다.
  >> 이 경우, "TOO SAFE"를 출력합니다.
• 그렇다면 진입차수가 모두 0이 아닌 경우라면 어떨까요? 이 경우, 버튼을 나타낸 그래프에서 싸이클이 존재한다고 볼 수 있습니다.
• 싸이클이 발생한 경우, 나올 수 있는 결과는 다음과 같습니다.
  (1) 모든 버튼이 하나의 집합으로 연결된 경우, 어느 버튼을 눌러도 금고가 열리기 때문에 "THIEF LOVE IT!"을 출력합니다.
  (2) 모든 버튼이 각각 싸이클이 존재하는 여러 집합으로 존재하는 경우, 한번에 금고를 여는 것이 불가능하기에 "TOO SAFE"를 출력합니다.
• 싸이클이 발생한 경우, 나올 수 있는 집합의 개수를 세야 합니다. 이 때, 분리집합 개념을 사용하면 쉽게 프로그래밍 할 수 있습니다.

 

소스코드

#include <stdio.h>
#define NMAX 1010
using namespace std;
 
// 입력 변수
int n;
int inpNum[NMAX][NMAX];
char inpDir[NMAX][NMAX];
 
// 그래프 변수
int pcnt;
int parent[NMAX*NMAX], check[NMAX*NMAX];
int enter[NMAX][NMAX];
 
// 결과 변수
int cnt, x, y;
 
int find(int p) {
    if(parent[p] == p) return p;
    else return parent[p] = find(parent[p]);
}
 
void connect(int i, int j) {
    int ii, jj, p, pp;
 
    // 숫자가 0인 경우 제외
    if(!inpNum[i][j]) return;
 
    // 버튼의 다음 값 탐색
    switch(inpDir[i][j]) {
        case 'U':
            ii = i-inpNum[i][j];
            jj = j;
            break;
 
        case 'D':
            ii = i+inpNum[i][j];
            jj = j;
            break;
 
        case 'L':
            ii = i;
            jj = j-inpNum[i][j];
            break;
 
        default:
            ii = i;
            jj = j+inpNum[i][j];
    }
 
    enter[ii][jj]++;
 
    // 집합으로 나누기
    p = find(i*n+j); pp = find(ii*n+jj);
 
    if(p == pp) return;
    else parent[p] = pp;
 
}
 
int main() {
    // 입력
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            scanf("%d%c", &inpNum[i][j], &inpDir[i][j]);
        }
    }
 
    // 분리집합 초기값
    for(int i=0;i<n*n;i++) parent[i] = i;
 
    // 그래프 그리기
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            connect(i, j);
        }
    }
 
    // 진입 차수 & 그래프 내 집합의 개수 파악하기
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            // 진입 차수
            if(!enter[i][j]) {
                cnt++;
                x = i+1; y = j+1;
            }
            
            // 집합의 개수
            if(!check[find(i*n+j)]) {
                check[find(i*n+j)] = 1;
                pcnt++;
            }
        }
    }
 
    // 결과 출력
    if(cnt == 1) printf("%d %d", x, y);
    else if(cnt > 1) printf("TOO SAFE");
    else {
        if(pcnt > 1) printf("TOO SAFE");
        else printf("THIEF LOVE IT!");
    }
 
}

 

후기

생각보다 시간이 걸렸던 문제였습니다. 특히 진입 차수가 0이 없으면 항상 "THIEF LOVE IT!" 이라고 생각했으나 "TOO SAFE"가 나오는 경우도 있다는 걸 깨닫는데 시간이 걸렸습니다. 분리집합과 그래프를 연습할 때 추천할만한 문제라고 생각합니다.