Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 완전탐색
- Network
- 시뮬레이션
- 세그먼트 트리
- 이분탐색
- 플로이드-와샬
- 알고리즘
- JUnit 5
- java
- 유니온 파인드
- 프로그래머스
- 백준
- dfs
- 후니의 쉽게 쓴 시스코 네트워킹
- CS
- BFS
- 에라토스테네스의 체
- Kotlin
- 스택
- 구현
- 동적계획법
- 문자열
- mst
- 위상정렬
- swea
- 그리디
- 백트래킹
- Effective Java
- 투 포인터
- 수학
Archives
반갑습니다!
[백준] 17472 다리 만들기 2 본문
풀이
[프로그래머스] 지형 이동과 유사한 문제인데 개인적으로 조금 더 까다로웠다. 상당히 구현할 것이 많은 문제이다. 해당 문제는 완전탐색으로도 해결할 수 있다고 한다. 아래의 코드는 MST를 사용해서 해결하였다.
이 문제에서 MST를 만들어서 문제를 해결하려면 크게 3단계로 나누어서 풀어야한다.
- 섬들 라벨링 하기
- 섬들 간의 거리 구하기
- MST 생성하기
우선 섬 라벨링은 BFS 알고리즘을 통해 할 수 있었다. visited[][]
배열을 선언해 중복 방문을 막아주었다.
// 섬들을 구분하기 위해 bfs 알고리즘 사용
void bfs(int x, int y, int idx) {
queue<pair<int, int>> q;
q.push({ x, y });
visited[y][x] = idx;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; // 범위를 벗어나는 경우
// 방문한 적 없고 육지인 경우
if (!visited[ny][nx] && board[ny][nx] == board[cur.second][cur.first]) {
q.push({ nx, ny });
visited[ny][nx] = idx;
}
}
}
}
그러면 visited[][]
배열에 섬들이 각자 라벨링 되어있게 되는데, 이제는 각 섬들간의 거리를 구해야 한다. 다리를 건설할 때 방향을 꺾으면 안된다는 조건이 있기 때문에 while문을 통해 어렵지 않게 구현할 수 있었다. 이 때 1번 섬에서 4번 섬까지 가는 거리나 4번 섬에서 1번 섬까지 가는 거리는 같은데 중복으로 저장될 수 있기 때문에 set
을 통해 중복된 간선을 제거해주었다.
void calculate_distance(int x, int y) {
for (int i = 0; i < 4; i++) {
int dist = 0;
int nx = x;
int ny = y;
int idx = visited[y][x];
while (true) {
nx += dx[i];
ny += dy[i];
int next_idx = visited[ny][nx];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || next_idx == idx) break;
if (next_idx != 0 && next_idx != idx) {
if (idx > next_idx) swap(idx, next_idx); // 섬은 작은 번호부터 큰 번호 순으로 저장
// 다리 길이가 1보다 길면 저장
if (dist > 1) s.insert({ dist, {idx, next_idx} });
break;
}
else dist++;
}
}
}
이제 섬들간의 거리를 모두 알게 되었으니 kruskal 알고리즘을 사용해서 MST를 생성할 수 있다. MST를 생성한 후, kruskal 알고리즘을 통해 계산한 값을 출력해주면 끝날 것 같지만 한 가지 주의해야할 것이 있다. 바로 모든 섬들이 연결되어있는지 확인해야 하는 것이다. 이는 유니온 파인드 구현할 때 구현한 find()
함수를 사용해 해결해주었다.
코드
C++
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 섬 연결하기 (0) | 2020.10.21 |
---|---|
[백준] 1915 가장 큰 정사각형 (0) | 2020.10.20 |
[백준] 6497 전력난 (0) | 2020.10.19 |
[백준] 4386 별자리 만들기 (0) | 2020.10.19 |
[백준] 14921용액 합성하기 (0) | 2020.10.14 |