21W31-구현 - 06 그래프의 기본과 탐색

[moodmine]

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV3FxxD6ABgBBARB

[murry2018]

SWEA 1249. 보급로

왜 DFS는 망했을까요?

#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>

using namespace std;

int _arr[10000];
int N;
int _cost[10000];

static inline int& arr(int r, int c) {
    return *(_arr + r*N + c);
}
static inline int& cost(int r, int c) {
    return *(_cost + r*N + c);
}
static inline void init_cost() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cost(i, j) = 1e9;
        }
    }
}

struct point {
    int r, c;
    point(int r, int c)
        :r(r), c(c) {
    }
};

static inline bool isvalid(int n) {
    return 0 <= n && n < N;
}

static void bfs() {
    static const int dr[4] = {1, 0, -1, 0};
    static const int dc[4] = {0, 1, 0, -1};

    queue<point> q;
    q.emplace(0, 0);
    cost(0, 0) = arr(0, 0);
    while (!q.empty()) {
        point& p = q.front();
        const int r = p.r;
        const int c = p.c;
        q.pop();
        for (int i = 0; i < 4; i++) {
            const int nr = r + dr[i];
            const int nc = c + dc[i];
            const int next_cost = cost(r, c) + arr(nr, nc);
            if (isvalid(nr) && isvalid(nc)
                && cost(nr, nc) > next_cost) {
                cost(nr, nc) = next_cost;
                q.emplace(nr, nc);
            }
        }
    }
}

static int compute_cost() {
    // clear_visit();
    init_cost();
    // return dfs(0, 0, 0);
    bfs();
    return cost(N-1, N-1);
}

int main() {
    int T;
    scanf("%d", &T);
    for (int c = 0; c < T; c++) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                scanf("%1d", &arr(i, j));
            }
        }
        int cost = compute_cost();
        printf("#%d %d\n", c+1, cost);
    }
}

[moodmine]

SWEA 1249. 보급로

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

#define INF 1000000

int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);

    for (test_case = 1; test_case <= T; ++test_case)
    {
        printf("#%d ", test_case);
        int size;
        scanf("%d", &size);

        char arr[100][101];
        for (int i = 0; i < size; i++)
        {
            scanf("%s", arr[i]);
        }

        int table[100][100];
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                table[i][j] = INF;
            }
        }

        table[0][0] = 0;
        int signal = 1;
        int temp = 0;

        while (signal)
        {
            signal = 0;

            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (j < size - 1)
                    {
                        temp = table[i][j] + (arr[i][j + 1] - 48);
                        if (table[i][j + 1] > temp)
                        {
                            table[i][j + 1] = temp;
                            signal = 1;
                        }
                    }

                    if (i < size - 1)
                    {
                        temp = table[i][j] + (arr[i + 1][j] - 48);
                        if (table[i + 1][j] > temp)
                        {
                            table[i + 1][j] = temp;
                            signal = 1;
                        }
                    }

                    if (j > 0)
                    {
                        temp = table[i][j] + (arr[i][j - 1] - 48);
                        if (table[i][j - 1] > temp)
                        {
                            table[i][j - 1] = temp;
                            signal = 1;
                        }
                    }

                    if (i > 0)
                    {
                        temp = table[i][j] + (arr[i - 1][j] - 48);
                        if (table[i - 1][j] > temp)
                        {
                            table[i - 1][j] = temp;
                            signal = 1;
                        }
                    }
                }
            }
        }

        printf("%d\n", table[size - 1] [size - 1]);
    }
    return 0;
}

[happy-oh]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<string.h>
#define MAX_VALUE 10000
using namespace std;
int T_depth;
int input_data[100][101];
int y_move[4] = { 0, 1, 0, -1 };
int x_move[4] = { 1, 0, -1, 0 };

int fill_matrix(int n)
{
    // 잘못된코드니 참고하지말아주세요
    int matrix[100][100];
    int idx, jdx, kdx, zdx;
    int last_num = 11;
    for (idx = 0; idx < n; ++idx)
    {
        for (jdx = 0; jdx < n; ++jdx)
        {
            matrix[idx][jdx] = MAX_VALUE;
        }
    }
    for (zdx = 1; zdx <= last_num; ++zdx)
    {
        for (idx = 0; idx < n; ++idx)
        {
            for (jdx = 0; jdx < n; ++jdx)
            {
                if ((idx == 0) && (jdx == 0))
                {
                    matrix[0][0] = 0;
                }
                else if ((idx == n - 1) && (jdx == n - 1))
                {
                    if (matrix[n - 2][n-1] < matrix[n-1][n - 2])
                        matrix[n-1][n-1] = matrix[n - 2][n-1];
                    else
                        matrix[n-1][n-1] = matrix[n-1][n - 2];
                    if (zdx == last_num)
                        return matrix[n-1][n-1];
                }
                else
                {
                    int x, y;
                    for (kdx = 0; kdx < 4; ++kdx)
                    {
                        x = jdx + x_move[kdx];
                        y = idx + y_move[kdx];
                        if (x < 0 || x >= n || y < 0 || y >= n) continue;
                        if (matrix[idx][jdx] > matrix[y][x] + input_data[idx][jdx])
                            matrix[idx][jdx] = matrix[y][x] + input_data[idx][jdx];
                    }
                }
            }
        }
    }

}

int main(void)
{
    // 잘못된코드니 참고하지말아주세요
    freopen("input.txt", "r", stdin);
    int T, N, test_case;
    char input_sdata[100][101];
    char temp_trash;

    int answer_value;
    scanf("%d", &T);
    int idx, jdx, kdx, mdx, ndx;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d%c", &N, &temp_trash);
        for (idx = 0; idx < N; ++idx)
        {
            for (jdx = 0; jdx <= N; ++jdx)
            {
                scanf("%c", &input_sdata[idx][jdx]);
                if (jdx < N)
                    input_data[idx][jdx] = input_sdata[idx][jdx] - '0';
                else
                    input_data[idx][jdx] = input_sdata[idx][jdx];

            }
        }
        answer_value = fill_matrix(N);
        printf("#%d %d\n", test_case, answer_value);

        /*
        printf("testcast : %d\n", test_case);

        for (idx = 0; idx < N; ++idx)
        {
            for (jdx = 0; jdx <= N; ++jdx)
            {
                if(jdx == N)
                    printf("%c", input_data[idx][jdx]);
                else
                    printf("%d", input_data[idx][jdx]);
            }
        }
        // */
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
```c++