[C언어 백준 풀이][Silver I] 2178번 : 미로 탐색 / 2667번 : 단지 번호 붙이기 / 1149번 : RGB 거리

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver I에 해당하는 문제들인 2178번 : 미로 탐색, 2667번 : 단지 번호 붙이기, 1149번 : RGB 거리를 풀이하도록 하겠습니다.

 

 

2178번 : 미로 탐색

 

미로에 대한 구조가 2차원 배열로써 주어질 때, 미로를 탈출하기 위해 (1, 1)의 좌표에서 목적지 (N, M)까지 이동하는 데 필요한 이동 거리를 구하는 문제입니다.

역시 배열의 크기 제한이 크지 않으므로 단순한 탐색 알고리즘으로 해결이 가능해보이는 문제입니다.

다만 미로 탐색의 최단 거리를 구해야 하기 때문에 DFS로는 풀면 안되고, BFS로 해결해야 합니다.

 

#include<stdio.h>

int map[105][105] = {0, }, visit[105][105] = {0, }, dist[105][105], queueX[10005] = {0, }, queueY[10005] = {0, }, N, M;

void BFS(int X, int Y) {
    int front = 0, rear = 1, popX, popY;
    visit[X][Y] = 1;
    queueX[0] = X, queueY[0] = Y;
    while(front < rear) {
        popX = queueX[front], popY = queueY[front++];
        if(map[popX+1][popY] && !visit[popX+1][popY]) {
            visit[popX+1][popY] = 1;
            dist[popX+1][popY] = dist[popX][popY]+1;
            queueX[rear] = popX+1;
            queueY[rear++] = popY;
        }
        if(map[popX-1][popY] && !visit[popX-1][popY]) {
            visit[popX-1][popY] = 1;
            dist[popX-1][popY] = dist[popX][popY]+1;
            queueX[rear] = popX-1;
            queueY[rear++] = popY;
        }
        if(map[popX][popY+1] && !visit[popX][popY+1]) {
            visit[popX][popY+1] = 1;
            dist[popX][popY+1] = dist[popX][popY]+1;
            queueX[rear] = popX;
            queueY[rear++] = popY+1;
        }
        if(map[popX][popY-1] && !visit[popX][popY-1]) {
            visit[popX][popY-1] = 1;
            dist[popX][popY-1] = dist[popX][popY]+1;
            queueX[rear] = popX;
            queueY[rear++] = popY-1;
        }
    }
}

int main() {
    int x, y;
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) scanf("%1d", &map[i][j]);
    dist[1][1] = 1;
    BFS(1, 1);
    printf("%d", dist[N][M]);
}

 

반복되는 코드가 조금 많은 경향이 있지만 코드의 이해를 돕기 위해 반복되는 부분도 그대로 작성했습니다.

기존의 BFS는 큐를 하나만 사용하면 되지만 미로에서는 x좌표와 y좌표를 모두 큐에 저장해야하기 때문에 큐를 2개 사용했습니다. (번호는 동일하게 사용)

탐색을 수행할 때 이동은 상하좌우로만 가능하므로 4개의 조건문을 사용하여 상하좌우에 이동할 수 있는 칸이 있는지 확인하고 있을 시에는 큐에 저장하도록 하여 현재 칸에서의 탐색이 끝난 이후에 탐색할 수 있도록 하였습니다.

거리는 탐색을 해나가면서 DP로 기록하였고, dist 배열에 이전 좌표 + 1이 되도록 거리를 기록하였습니다.

 

 

2667번 : 단지 번호 붙이기

 

이전의 배추 문제와 같이 1로 이루어진 덩어리가 몇 개인지 찾고, 여기에 추가된 조건으로 단지에 속하는 가구의 수가 적은 순서대로 오름차순으로 그 수를 출력해야 하는 문제입니다.

탐색 부분은 DFS로 쉽게 해결이 가능하고 단지의 가구 수를 오름차순으로 정렬만 해주면 될 것 같습니다.

 

#include<stdio.h>

int N, map[30][30] = {0, }, visit[30][30] = {0, }, households[900] = {0, }, var[3][5] = {{1, -1, 0, 0}, {0, 0, 1, -1}}, count = 1, temp;

void DFS(int X, int Y) {
    visit[X][Y] = 1;
    households[count]++;
    for(int i=0; i<4; i++) if(map[X+var[0][i]][Y+var[1][i]] && !visit[X+var[0][i]][Y+var[1][i]]) DFS(X+var[0][i], Y+var[1][i]);
}

int main() {
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) scanf("%1d", &map[i][j]);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) if(map[i][j] && !visit[i][j]) DFS(i, j), count++;
    printf("%d\n", --count);
    for(int i=1; i<=count; i++)
        for(int j=i+1; j<=count; j++)
            if(households[i] > households[j]) {
                temp = households[i];
                households[i] = households[j];
                households[j] = temp;
            }
    for(int i=1; i<=count; i++) printf("%d\n", households[i]);
}

 

DFS 함수에서 상하좌우를 한 번씩 체크해줘야 하는데 이 부분에서 반복되는 코드를 배열을 이용해서 간략화시켰습니다.

좌표에서 1을 더하고 빼는 부분을 var 함수를 이용해서 적절히 덧셈 뺄셈을 해줄 수 있도록 작성했습니다.

각 덩어리의 가구 수는 households 배열에 저장되어 있고, 이는 count 변수를 이용해서 배열 칸을 옮길 수 있도록 하였습니다.

DFS만 사용할 줄 안다면 어렵지 않은 문제였습니다.

 

 

1149번 : RGB 거리

 

N개의 집이 일렬로 위치해 있을 때, 한 집의 색이 양 옆 집의 색과 달라야 한다면 집을 칠할 수 있는 최소 비용이 얼마인지를 계산하는 문제입니다.

제한 시간 안에 코드가 작동하기 위해서는 i번째 집까지의 비용의 최솟값들을 저장하면서 비교해나가야 합니다.

따라서 이 문제는 DP(동적 프로그래밍)을 이용하여 풀어야하는 문제입니다.

 

#include<stdio.h>

int min(int a, int b) { return a<b?a:b; }

int main() {
    int N, eachCost[1005][3], minCost[1005][3];
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d %d %d", &eachCost[i][0], &eachCost[i][1], &eachCost[i][2]);
    for(int i=0; i<3; i++) minCost[1][i] = eachCost[1][i];
    for(int i=2; i<=N; i++) {
        minCost[i][0] = min(minCost[i-1][1], minCost[i-1][2]) + eachCost[i][0];
        minCost[i][1] = min(minCost[i-1][2], minCost[i-1][0]) + eachCost[i][1];
        minCost[i][2] = min(minCost[i-1][0], minCost[i-1][1]) + eachCost[i][2];
    }
    printf("%d", min(min(minCost[N][0], minCost[N][1]), minCost[N][2]));
}

 

우선 각 비용(eachCost)을 입력받고, 집이 1개일 때는 어쨌든 경우의 수가 한 가지 밖에 없으니 minCost[0]에 eachCost[0]을 저장해줍니다.

그 다음 각 minCost를 계산할건데, i-1번째 집의 minCost 2가지 중에서 더 작은 것에 i번째 eachCost를 합한 것이 해당 색으로 i번째 집을 칠할 때 드는 총 비용의 최솟값이 될 것입니다.

따라서 이와 같은 방법으로 N번째 집까지 계산을 해주면 총 3가지의 경우의 수가 나오는데 (N번째 집이 R, G, B 중 하나로 칠해지는 경우) 이들 중 가장 작은 비용이 N개의 집을 칠하는 최소 비용이 됩니다.