BOJ 5213 · 과외맨 — PROJECT REBAS

알고리즘 분류 : BFS

BFS를 통해 최단 거리를 구하는 문제다. 일반적인 BFS 문제와 다르게, 주어지는 입력 데이터가 굉장히 골치 아프다. 입력 데이터를 인접 행렬로 적절하게 변환하는 과정이 필요하다.

우선 주어지는 입력 데이터를 2차원 인접 행렬로 변환한다. 하나의 타일은 2 조각으로 나누어져 있으므로, 세로 N개 가로 N*2개이다. 따라서 인접 행렬을 a[N][N*2]로 선언한다.
입력 데이터를 인접 행렬에 넣을 때, 홀수 줄, 짝수 줄에 따라 다르게 넣어야 한다. 홀수 줄에서는 2*N개의 데이터를 모두 넣는다. 짝수 줄에서는 앞뒤로 한 칸씩 0으로 비워놓고, 안쪽에 2*N-1개의 데이터를 넣는다. 데이터는 총 N*N-N/2줄에 2개씩 들어온다.
인접 행렬을 만들면서 각 타일의 레벨 값을 저장할 배열 b를 a와 같은 사이즈로 선언한다.
b 배열은 a와 마찬가지로 홀수 줄과 짝수 줄을 구분해야 한다. 홀수 줄에는 N개의 레벨이 있고, 짝수 줄에는 N-1개의 레벨이 있다.
a와 b 배열을 모두 만들었다면, 이를 바탕으로 인접 리스트 v를 생성한다. 하나의 타일에서 상하좌우로 탐색하면서 더 나아갈 수 있는 타일이 있다면, 그 타일에 인접 리스트로 연결한다.
넘어갈 수 있는 타일은, 같은 레벨일 경우와, 다른 레벨일 때 같은 숫자일 경우이다.
인접리스트 v를 바탕으로 BFS 탐색을 하고, BFS 탐색을 하면서 이동 경로를 저장한다.
이동 경로는 BFS 탐색을 진행하면서 현재 위치에 이전 위치를 넣으면서 저장할 수 있고, BFS 탐색 종료 후 역순으로 출력하면 된다.
마지막 도착 지점은 타일 레벨이 제일 큰 곳이므로, 이전에 저장한 레벨보다 큰 레벨에 도착할 때 업데이트하면 된다.

C++ 소스코드

#include <cstdio>
#include <vector>
#include <queue>
#define MAX 505
#define MAX_TILE 255000
using namespace std;

int n, m, ans;
int a[MAX][MAX*2], b[MAX][MAX*2];
int path[MAX_TILE];
bool check[MAX_TILE];
vector<int> v[MAX_TILE];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void input() {
    // Make adjacent matrix.
    scanf("%d",&n);
    m = n*2;
    int index = 1;
    for (int i=0; i<n; i++) {
        int k = i & 1;
        for (int j=k; j<m-k; j++) {
            scanf("%d", &a[i][j]);
            b[i][j] = index;
            index += ((j+k) & 1);
        }
    }
}

void graph() {
    // Make adjacent list.
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            int now = b[i][j];
            for (int k=0; k<4; k++) {
                int ni = i+dx[k], nj = j+dy[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
                int next = b[ni][nj];
                if (now != next && a[i][j] == a[ni][nj]) {
                    v[now].push_back(next);
                }
            }
        }
    }
}

void bfs() {
    queue<int> q;
    q.push(1);
    check[1] = true;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (auto nx : v[x]) {
            if (check[nx]) continue;
            if (ans < nx) ans = nx;
            check[nx] = true;
            path[nx] = x;
            q.push(nx);
        }
    }
}

void print() {
    // Print distance and path.
    vector<int> p;
    int x = ans;
    p.push_back(x);
    while (path[x]) {
        x = path[x];
        p.push_back(x);
    }
    int len = p.size();
    printf("%d\n", len);
    for (int i=0; i<len; i++) printf("%d ", p[len-i-1]);
    printf("\n");
}

int main() {
    input();
    graph();
    bfs();
    print();
    return 0;
}

✓ 디버그 하는데 꽤 고생한 문제라서 별도로 디버그 함수를 만들었다.

✓ 아래 debug 함수를 통해서 입력 데이터, 변환한 인접 행렬, 변환한 인접 리스트를 확인할 수 있다.

void debug() {
    printf("\n");
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            printf("%2d ", a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            printf("%2d ", b[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for (int i=1; i<=n*n-n/2; i++) {
        printf("%d : ", i);
        for (auto k : v[i]) {
            printf("%d ", k);
        }
        printf("\n");
    }
}

Python 3 소스코드

from sys import stdin, stdout
from collections import deque
input = stdin.readline
print = stdout.write

n = int(input())
m, t = n*2, n*n-n//2+1
a = [[0]*m for _ in range(n)]
b = [[0]*m for _ in range(n)]
v = [[] for _ in range(t)]
path = [0 for _ in range(t)]

def init():
    temp = []
    for _ in range(t-1):
        temp.extend(list(map(int, input().split())))
    cnt, idx = 0, 1
    for i in range(n):
        k = i & 1
        for j in range(k, m-k):
            a[i][j] = temp[cnt]
            b[i][j] = idx
            cnt += 1
            idx += ((j+k) & 1)

def graph():
    for i in range(n):
        for j in range(m):
            now = b[i][j]
            for di, dj in (-1, 0), (1, 0), (0, -1), (0, 1):
                ni, nj = i+di, j+dj
                if ni < 0 or ni >= n or nj < 0 or nj >= m:
                    continue
                nxt = b[ni][nj]
                if now != nxt and a[i][j] == a[ni][nj]:
                    v[now].append(nxt)

def bfs(ans):
    q = deque()
    check = [False]*t
    q.append(1)
    check[1] = True
    while q:
        x = q.popleft()
        for nx in v[x]:
            if not check[nx]:
                ans = max(ans, nx)
                check[nx] = True
                path[nx] = x
                q.append(nx)
    return ans

def result(ans):
    p = [ans]
    x = ans
    while path[x]:
        x = path[x]
        p.append(x)
    print(str(len(p))+'\n')
    p.reverse()
    print(' '.join(map(str, p))+'\n')


init()
graph()
result(bfs(0))

참고

백준 온라인 저지 : BOJ 5213

저작자표시 비영리 변경금지

티스토리툴바

BOJ 5213 · 과외맨

티스토리툴바