문제 설명

• 부등호에 맞춰서 1~9 숫자 퍼즐을 완성하는 문제
• 입력 : 퍼즐의 한 변의 길이, 부등호의 모양
• 출력는 퍼즐의 모양으로 출력
  • 1 2 3 4 5 6 7 8 9 이러한 예시로 출력
• 가능한 답이 여러 가지라면 그 중 아무거나 출력

문제 해결 Key_point

• 위상 정렬을 사용해야 함
• 위상 정렬이란?
  • 방향 비순환 그래프에서 노드들을 정렬하는 알고리즘
  • 그럼 방향 비순환 그래프는 또 무엇일까?
    • 간선의 방향이 존재하는 그래프 중에 사이클이 없는 그래프
  • 특징
    1. 방향 그래프에서만 수행 가능
    2. 사이클이 존재하면 위상 정렬을 수행할 수 없음
    3. 여러 개의 정렬 결과가 존재할 수 있음
    4. 대표적으로 작업 스케줄링, 선수 과목 문제에서 활용
  • 알고리즘
    • 진입 차수(indegree)를 용하는 칸 알고리즘(큐 방식)과 DFS(스택 방식) 두 가지 방법으로 구현 가능

문제 해결 아이디어

• 퍼즐을 그래프로 모델링
  • 각 퍼즐의 칸을 노드로 보고, 부등호를 간선으로 변환하여 방향 그래프 만들기

  • 가 있다면 오른쪽 숫자가 더 크다 → (오른쪽 노드 → 현재 노드) 방향의 간선 추가

  • < 가 있다면 왼쪽 숫자가 더 크다 → (현재 노드 → 오른쪾 노드) 방향의 간선 추가
  • 이러한 방식으로 가로 세로 부등호 처리
  • 그리고 각 노드의 진입 차수를 계산 (진입 차수가 0인것부터 시작해야함으로 알아야 함)
• 위상 정렬을 이용하여 퍼즐 숫자 채우기
  • 진입 차수가 0인 노드를 큐에 삽입
  • 큐에서 노드를 하나씩 꺼내며 숫자를 채움
  • 현재 노드와 연결된 노드들의 진입 차수 감소
  • 모든 노드들 처리할 때까지 반복
• 위상 정렬이 끝난 이후 퍼즐 배열에 있는 값 출력!

소스 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N; // 퍼즐 수
vector<int> adj[1000 * 1000 + 1]; //인접 리스트 2차원 그래프
int in_degree[1000 * 1000 + 1]; //진입 차수 배열(0인것부터 시작해야 함)
int puzzle[1001][1001];//결과를 저장하기 위한 배열
queue<int> q; //위상 정렬을 위한 큐

//퍼즐을 채우는 함수
void fill_puzzle(int loc, int num) {
    int x = (loc - 1) / N + 1;
    int y = (loc - 1) % N + 1;
    puzzle[x][y] = num;
}
//위상 정렬 함수
void topological_sort() {
    int num = 1;
    while (!q.empty()) { //큐가 빌때까지
        int curr = q.front(); //큐에 값 추출하고(현재 노드 빼기)
        q.pop();
        fill_puzzle(curr, num++); //퍼즐에 넣기
        for (int next : adj[curr]) { //현재 노드와 ㅇ녀결된 노드들의 진입 차수 감소
            in_degree[next]--;
            if (in_degree[next] == 0) q.push(next); //진입 차수가 0이면 큐에 추가
        }
    }
}

int main() {
    cin >> N;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j < N; j++) {
            char sign;
            cin >> sign;
            int curr = (i - 1) * N + j;
            int right = curr + 1;
            if (sign == '>') {
                adj[right].push_back(curr);
                in_degree[curr]++;
            } else {
                adj[curr].push_back(right);
                in_degree[right]++;
            }
        }
    }

    for (int i = 1; i < N; i++) {
        for (int j = 1; j <= N; j++) {
            char sign;
            cin >> sign;
            int curr = (i - 1) * N + j;
            int down = curr + N;
            if (sign == '>') {
                adj[down].push_back(curr);
                in_degree[curr]++;
            } else {
                adj[curr].push_back(down);
                in_degree[down]++;
            }
        }
    }

    for (int i = 1; i <= N * N; i++) {
        if (in_degree[i] == 0) q.push(i);
    }

    topological_sort();

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << puzzle[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}ㄴ

소감

솔직히 혼자 풀라고 했으면 못 풀었다. 친구에게 물어보고 chatgpt에게 힌트를 달라고 해서 문제를 해결했다. 추가로 블로그 글도 참고하여 문제를 풀었다.

도움 : 박연종