Algorithm/Baekjoon

[Algorithm]Baekjoon 1261번 :: 알고스팟

MaxLevel 2023. 10. 12. 10:25

https://www.acmicpc.net/problem/1261

 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct Node
{
    int y;
    int x;
};
 
int n, m;
int arr[100][100];
int dist[100][100];
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
void BFS()
{
    memset(dist, 0x3f, sizeof(dist));
 
    queue<Node> q;
    q.push({ 0,0 });
    dist[0][0] = 0;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (nextY < 0 || nextY == n) continue;
            if (nextX < 0 || nextX == m) continue;
 
            if (dist[curY][curX] + arr[nextY][nextX] < dist[nextY][nextX])
            {
                dist[nextY][nextX] = dist[curY][curX] + arr[nextY][nextX];
                q.push({ nextY,nextX });
            }
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> m >> n;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        for (int j = 0; j < s.size(); ++j)
        {
            arr[i][j] = s[j] - '0';
        }
    }
 
    BFS();
 
    cout << dist[n - 1][m - 1];
}
 cs

내가 어떤 유형에 약한지 알 수 있었던 문제.. 

문제난이도를 객관적으로 봤을땐 사실 빨리 풀었어야했는데 그러지 못했다.

생각해보니 네오플코테 봤을때도 이런 유형이였던거같은데...