Game Develop

[Algorithm] Baekjoon 2146번 : 다리 만들기 본문

Algorithm/Baekjoon

[Algorithm] Baekjoon 2146번 : 다리 만들기

MaxLevel 2023. 3. 1. 00:26

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

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
struct Node
{
    int y;
    int x;
};
 
int n;
int arr[101][101];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<vector<Node>> allNodes;
vector<Node> tempNodes;
int result = 10000000;
 
void SaveAllNodes(int sy, int sx)
{
    queue<Node> q;
    q.push({ sy,sx });
    arr[sy][sx] = 2; // 방문체크.
    tempNodes.push_back({ sy,sx });
 
    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 + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= n) continue;
            if (arr[nextY][nextX] == 0) continue;
            if (arr[nextY][nextX] == 2) continue;
 
            arr[nextY][nextX] = 2;
            q.push({ nextY,nextX });
            tempNodes.push_back({ nextY,nextX });
        }
    }
}
 
int FindShortestDistance(int index1, int index2)
{
    int shortestDistance = 1000000;
 
    for (int i = 0; i < allNodes[index1].size(); ++i)
    {
        Node t1 = allNodes[index1][i];
 
        for (int j = 0; j < allNodes[index2].size(); ++j)
        {
            Node t2 = allNodes[index2][j];
 
            int dist = abs(t1.y - t2.y) + abs(t1.x - t2.x);
            shortestDistance = min(shortestDistance, dist);
        }
    }
 
    return shortestDistance - 1;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    
    cin >> n;
    int islands = 0;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (arr[i][j] == 1)
            {
                ++islands;
                tempNodes.clear();
               SaveAllNodes(i, j);
                allNodes.push_back(tempNodes);
            }
        }
    }
    
    for (int i = islands -1; i >= 0; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            result = min(result, FindShortestDistance(i, j));
        }
    }
    
    cout << result;
}
 cs

 

 

풀었던 골3짜리 문제들중에선 제일 빨리 푼 문제인듯 하다.

각 덩어리들 사이의 짧은 거리를 구하는 문제인데, 고민 좀 하다가 n 최댓값이 100밖에 안된다는 걸 알고 그냥 일일이 비교하는 식으로 했더니 통과했다.

 

로직은 간단하다.

1. 각 섬마다의 노드 좌표값들을 따로 저장(allNodes)

2. 이후 중복 안되는 선에서 각 노드들 전부 비교.

    -> 1번섬이랑 2번섬이랑 비교를 했다면, 이후 2번섬 입장에서 또 1번섬을 검사할이유는 없다. 이미 두 섬의 최단거리는           구했으니까

 

문제 제한시간은 2초인데 n이 100밖에 안되기 때문에 일단 통과는 될거라 생각하고 코드를 작성했다.

결과는 96ms 나오면서 통과했다.

 

근데 사실 이건 n값이 작아서 그런거고, 당장 될거같아서 일일이 다 검사하는식으로 해봤다.

n값이 커지면 결국 큐로 검사하는식으로 해야 시간이 더 단축될 것 같다.

그래서 한 섬의 노드를 각 섬마다의 큐에 전부 넣어놓고 BFS탐색으로 다른 대륙까지의 최단거리를 구하게 해봤다.

 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
struct Node
{
    int y;
    int x;
    int islandNum;
    int count;
};
 
int n;
int arr[101][101];
int tempMap[101][101];
int visited[101][101];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
vector<queue<Node>> allNodes;
int result = 10000000;
 
queue<Node> NumberTheIslands(int sy, int sx, int islandNum)
{
    queue<Node> tempQueue;
    queue<Node> q;
    q.push({ sy,sx,islandNum });
    arr[sy][sx] = islandNum; // 방문체크.
    tempQueue.push({ sy,sx,islandNum });
 
    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 + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= n) continue;
            if (arr[nextY][nextX] == 0) continue;
            if (arr[nextY][nextX] == islandNum) continue;
 
            arr[nextY][nextX] = islandNum;
            q.push({ nextY,nextX });
            tempQueue.push({ nextY,nextX,islandNum });
        }
    }
 
    return tempQueue;
}
 
int FindShortestDistance(int index) // 한 섬 전부.
{
    int answer = 10000000;
    int curIsland = allNodes[index].front().islandNum;
 
    while (!allNodes[index].empty())
    {
        memcpy(tempMap, arr, sizeof(arr));
        Node startNode = allNodes[index].front();
        startNode.count = 0;
        allNodes[index].pop();
 
        queue<Node> q;
        q.push(startNode);
 
        while (!q.empty())
        {
            int curY = q.front().y;
            int curX = q.front().x;
            int curCount = q.front().count;
            q.pop();
 
            for (int i = 0; i < 4; ++i)
            {
                int nextY = curY + dir[i][0];
                int nextX = curX + dir[i][1];
 
                if (nextY < 0 || nextY >= n) continue;
                if (nextX < 0 || nextX >= n) continue;
                if (tempMap[nextY][nextX] == curIsland) continue; // 방문체크
 
                if (tempMap[nextY][nextX] != 0) // 다른대륙이면
                {
                    answer = min(answer, curCount);
                    break;
                }
 
                tempMap[nextY][nextX] = curIsland;
                q.push({ nextY,nextX,curIsland,curCount + 1 });
            }
        }
    }
 
    return answer;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    
    cin >> n;
    int islands = 1;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (arr[i][j] == 1)
            {
                ++islands;
                allNodes.push_back(NumberTheIslands(i, j, islands));
            }
        }
    }
    
    for (int i = 0; i < islands - 1; ++i)
    {
        result = min(result, FindShortestDistance(i));
    }
    
    cout << result;
}
 cs

 

뭔가 복잡해보이는데 그냥 각 섬마다 번호 매긴 후, 각 섬에서의 모든 노드로부터 BFS 탐색을 시작해서 다른 섬의 최단거리를 구하는 로직이다.

근데 첫번째 로직과 수행속도가 똑같이 나왔다. 

n값이 커지면 그래도 좀 더 빠를거 같긴한데, 여기서 더 줄일 방법이 없나 생각해봤다.

 

좀 더 생각해보니, 특정 섬 기준으로 노드들을 뻗어갔을 때, 이미 다른 곳에서 뻗어져 나온 노드가 더 적은 count로 해당 지점을 방문했었을 경우 굳이 그 지점을 또 방문해서 뻗어나갈 필요가 없다.

그래서 int visited[101][101]을 추가로 선언해줘서 각 칸마다의 count값을 기록해놨다. 

각 섬마다가 기준이기 때문에, FindShortestDistance를 호출할 때마다 큰 값으로 초기화 해줬다.

 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
struct Node
{
    int y;
    int x;
    int islandNum;
    int count;
};
 
int n;
int arr[101][101];
int tempMap[101][101];
int visited[101][101];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
vector<queue<Node>> allNodes;
int result = 10000000;
 
queue<Node> NumberTheIslands(int sy, int sx, int islandNum)
{
    queue<Node> tempQueue;
    queue<Node> q;
    q.push({ sy,sx,islandNum });
    arr[sy][sx] = islandNum; // 방문체크.
    tempQueue.push({ sy,sx,islandNum });
 
    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 + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= n) continue;
            if (arr[nextY][nextX] == 0) continue;
            if (arr[nextY][nextX] == islandNum) continue;
 
            arr[nextY][nextX] = islandNum;
            q.push({ nextY,nextX });
            tempQueue.push({ nextY,nextX,islandNum });
        }
    }
 
    return tempQueue;
}
 
int FindShortestDistance(int index) // 한 섬 전부.
{
    int answer = 10000000;
    int curIsland = allNodes[index].front().islandNum;
    memset(visited, 0x3f, sizeof(visited));
 
    while (!allNodes[index].empty())
    {
        memcpy(tempMap, arr, sizeof(arr));
        Node startNode = allNodes[index].front();
        startNode.count = 0;
        allNodes[index].pop();
 
        queue<Node> q;
        q.push(startNode);
 
        while (!q.empty())
        {
            int curY = q.front().y;
            int curX = q.front().x;
            int curCount = q.front().count;
            q.pop();
 
            for (int i = 0; i < 4; ++i)
            {
                int nextY = curY + dir[i][0];
                int nextX = curX + dir[i][1];
 
                if (nextY < 0 || nextY >= n) continue;
                if (nextX < 0 || nextX >= n) continue;
                if (tempMap[nextY][nextX] == curIsland) continue; // 방문체크
                if (visited[nextY][nextX] <= curCount + 1) continue;
 
                if (tempMap[nextY][nextX] != 0) // 다른대륙이면
                {
                    answer = min(answer, curCount);
                    break;
                }
 
                tempMap[nextY][nextX] = curIsland;
                visited[nextY][nextX] = curCount + 1;
                q.push({ nextY,nextX,curIsland,curCount + 1 });
            }
        }
    }
 
    return answer;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    int islands = 1;
    memset(visited, 0x3f, sizeof(visited));
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (arr[i][j] == 1)
            {
                ++islands;
                allNodes.push_back(NumberTheIslands(i, j, islands));
            }
        }
    }
    
    for (int i = 0; i < islands - 1; ++i)
    {
        result = min(result, FindShortestDistance(i));
    }
    
    cout << result;
}
 cs

코드가 크게 달라진 건 없고, int visited[101][101]의 추가 선언과 FindShortestDistance()에서 노드를 퍼뜨리기위한 추가조건, 그리고 visited의 초기화밖에 없다.

 

해당 최적화를 하기전에는 96ms가 나왔는데 최적화를 적용하고 나니까 32ms가 나왔다. 3배정도 수행속도가 빨라졌다.

이런식으로 칸마다 카운팅해서 더이상 안퍼지게 하는건 BFS문제에서 꽤 자주 나오는 유형이라 익혀놓는게 좋다.

 

'Algorithm > Baekjoon' 카테고리의 다른 글

[Algorithm] Baekjoon 16933번 : 벽 부수고 이동하기3  (1) 2023.03.02
[Algorithm] Baekjoon 14442번 : 벽 부수고 이동하기2  (0) 2023.03.01
[Algorithm] Baekjoon 9466번 : 텀 프로젝트  (1) 2023.02.28
[Algorithm] Baekjoon 6593번 : 상범 빌딩  (0) 2023.02.27
[Algorithm] Baekjoon 7562번 : 나이트의 이동  (0) 2023.02.27
'Algorithm/Baekjoon' Related Articles more