BOJ_17472_다리만들기2 [Brute forcing by DFS]

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving

---

 우선 이 문제는 여러 방법으로 풀 수 있는 것 같다. 혹자는 MST로 풀어버리던데... 문제를 풀고 나서 다른 사람 코드를 보면서 이걸 '어케 MST라고 판단했지?' 하는 생각이 들었다. 나는 MST로 푼다는 생각 자체를 하지 못했다. 당연히 DFS로 완전 탐색 돌리는 거라고 생각했는데 생각해보니 참 신박하다. 뭐, 어쨌든 문제를 보니 input이 워낙 작기 때문에 애초에 완전 탐색을 유도한 문제라고 생각했기에 MST라고 생각하지 못한 것에 대한 억지 위로를 하였다. (뭐 어쨌든 MST도 거리 계산할 때 완전 탐색 할듯?)

 

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

17472번: 다리 만들기 2

 

 문제 자체만 보면 사실 어려운 난이도가 아니다. 다만 따져주저야 할 조건이 생각보다는 까다롭기 때문에 충분히 어려운 문제다. 나도 너무나 당연하게 처리했다고 생각한 조건 하나를 빼먹어서 5번이나 틀렸다. 실제 시험이었으면 뇌정지 강하게 와서 절대 못 찾았을 듯 ㅅㅂ... 

---

1. 인접한 섬 번호 매기기

 아무튼! 우선 당연하게도 연결된 섬들의 번호를 매겨주어야 한다. dfs로 번호를 매겼다. 이건 어려운 것이 전혀 없을 것이다. 물론 이때, islands 번호에 해당하는 벡터에 좌표를 전부 넣어준다.

 

// dfs는 섬 번호를 매기기 위함
void dfs(int y, int x, int numbering) {
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir], nx = x + dx[dir];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m || !map[ny][nx]) {
			continue;
		}
		if (visited[ny][nx] && map[ny][nx]) continue;

		visited[ny][nx] = true;
		map[ny][nx] = numbering;
        
        	// 좌표 넣기!
		islands[numbering].emplace_back(ny, nx);
		dfs(ny, nx, numbering);
	}
}

	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	// 인접한 섬들 번호 매김
	numbering = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] && !visited[i][j]) {
				map[i][j] = numbering;
				visited[i][j] = true;
				islands[numbering].emplace_back(i, j);
				dfs(i, j, numbering);
				numbering++;
			}
		}
	}
   	numbering--;

---

2 - 1. 완전 탐색 Base case

 나는 항상 N과 M 문제집을 강조한다. 일단 이걸 못 풀면 탐색 문제는 절대(아마도) 못푼다. 그러니까 꼭 풀도록 하자. 여기서 사용하는 기법과 완전히 동일하다. 그러니까 이거는 제발 꼭! 풀자. 결국 삼성 문제는 이 문제의 응용 문제 수준이다.

 

https://www.acmicpc.net/workbook/view/2052

문제집: N과 M (baekjoon)

 

 자꾸 잔소리가 길어지는데, 아무튼, 우리는 1~numbering 까지 모든 섬에 대해서 다 연결을 해보아야 한다. 이걸 for문을 통해 재귀로 탐색한다. 이게 무슨 소린지 이해 못하면 N과 M으로 반드시 돌아가라. 아무튼 그것을 다음과 같이 해결한다.

 

우선 solve(0, 0, map)이 뭘까.

 

 첫 번째 0은 탐색을 시작할 인덱스 - 1 이다. 왜 - 1을 했는지 모르는가? N과 M으ㄹ..읍읍

1번부터 탐색해야 하므로 0을 주었고 for(int i = idx + 1; i <= numbering; i++) 로 전부 탐색한다.

 

 두 번째 0은 현재 연결된 다리 개수이다.

 

 세 번째 map은 map 상태를 넘겨준다. 일단 다리를 놓아보고 안되면 빠꾸(?)를 쳐야하기 때문이다.

 

	solve(0, 0, map);
	if (ans == 100000) ans = -1;
	cout << ans;

void checkDfs(int cur, int& cnt) {
	for (int next : graph[cur]) {
		if (!check[next]) {
			check[next] = true;
			cnt++;
			checkDfs(next, cnt);
		}
	}
}

void solve(int idx, int bridge, int map[][10]) {
	// adj는 1번 섬부터 checkDfs로 탐색가능한 섬 개수
	int adj = 1;
	memset(check, 0, sizeof(check));
	check[1] = true;
	checkDfs(1, adj);
	// 1번 섬으로부터 전부 탐색 가능하면 답 갱신
	if (adj == numbering) {
		ans = min(ans, bridge);
		return;
	}

 

 자 이제, 하나 하나 살펴보자. idx는 탐색을 시작할 섬 번호 -1 이라고 했다. 그에 앞서서 일단 Base case를 정해야 한다. Base case는 모~~든 섬이 연결되어 있을 때이다. 이 코드 밑에서 다리가 놓아지면 연결시키는 부분은 있을 것이라 가정하고 일단 Base case를 설계하는 것이 핵심이다.

 

 어디서 시작하든 상관없지만 1번 섬부터 탐색한다고 하자. int adj = 1은 현재 1번 섬은 탐색 가능하기 때문에 1로 설정하였고, 1번부터 시작하므로 check[1]도 true로 설정하였다. (check배열은 checkDfs를 돌 때 사용할 visit 배열임) checkDfs를 통해 탐색할 때마다 adj를 증가시키고 adj가 numbering과 같다면 모든 섬을 연결한 것이므로 답을 갱신하고 return한다!

 

 그게 아니라면 이제 다음 것도 연결해 봐야 하기 때문에 밑으로 내려간다. 근데 밑 부분은 조금 길다. 숨 크게 들이 마시고~ 허업.

---

2 - 2. 완전 탐색

	// 모든 섬에 대해 탐색
	for (int i = idx + 1; i <= numbering; i++) {
		// 각 섬의 땅에 대해서 하나 씩 뽑아서 네 방향 탐색
		for (auto& cand : islands[i]) {
			int y = cand.first, x = cand.second;
			for (int dir = 0; dir < 4; dir++) {
				// 다음 칸과 다다음 칸에 다리를 놓을 수 없으면 탐색 안함
				int ny = y + dy[dir], nx = x + dx[dir];
				int nny = ny + dy[dir], nnx = nx + dx[dir];
				if (ny < 0 || ny >= n || nx < 0 || nx >= m || map[ny][nx] == i) continue;
				if (nny < 0 || nny >= n || nnx < 0 || nnx >= m || map[nny][nnx] == i) continue;
				// 다음 칸 혹은 다다음 칸에 섬이 있어도 탐색 안함
				if ((0 < map[ny][nx] && map[ny][nx] < 9) || 0 < map[nny][nnx] && map[nny][nnx] < 9) continue;

				// count는 현재 점에서 놓는 다리 개수
				int count = 0;

				// fail은 다리를 놓을 수 있는지 없는지
				bool fail = false;

				// map 보존을 위해
				int temp[10][10];
				memcpy(temp, map, sizeof(temp));

				// opposite는 다리를 놓을 수 있을 때 다리가 놓여진 상대 섬
				int opposite;
				while (true) {
					// ny, nx 부터 다리 놓음
					temp[ny][nx] = 9;
					count++;
					int temp_y = ny + dy[dir], temp_x = nx + dx[dir];

					// 바다 벗어나거나, 본인 섬에 닿으면 실패
					if (temp_y < 0 || temp_y >= n || temp_x < 0 || temp_x >= m || map[temp_y][temp_x] == i) {
						fail = true;
						break;
					}
					// 본인 섬이 아니고 다른 섬에 다다랐으면 성공
					if (map[temp_y][temp_x] != i && 0 < map[temp_y][temp_x] && map[temp_y][temp_x] < 9) {
						opposite = map[temp_y][temp_x];
						break;
					}
					ny = temp_y;
					nx = temp_x;
				}

				// 다리 놓을 수 있을 때
				if (!fail) {
					// 연결 안되어 있으면 연결
					if (!connected[i][opposite]) {
						connected[i][opposite] = true;
						connected[opposite][i] = true;
						graph[i].push_back(opposite);
						graph[opposite].push_back(i);
						solve(i, bridge + count, temp);
						graph[i].pop_back();
						graph[opposite].pop_back();
						connected[i][opposite] = false;
						connected[opposite][i] = false;
					}
				}
			}
		}
	}
}

 설명하긴 조금 힘들기에 주석으로 설명해 놓았다. 큰 틀은 이렇다. 첫 번째 for(int i = idx + 1; i <= numbering; i++) 로 모든 섬에 대해서 한 번씩 연결을 하게 된다. 이때 각각의 i번 섬에 해당하는 모든 섬의 좌표에 대해 다리를 놓아보는 것이 두 번째 for(auto &cand : islands[i]) 이다.

 

 그리고 그 밑에 while(true)가 나오기 전까지는 전부 조건이다. 일단 나는 다리를 놓았으면 9로 놓았다. ( -1로 설정할 수 있지만 -1로 두면 디버그 모드에서 조사식 볼 때 너비 바뀌어서 짜증남) 아무튼 조건을 통과한다면, 다리를 놓아 '본다', 그러니까 'try'이기 때문에 map을 실제로 바꾸는 것이 아니라 map을 복사해서 temp에다가 다리를 놓는 것이다. 아무튼 다리를 놓다가 성공하면 재귀로 한 번 더 들어가서 다음 섬을 탐색하고, 안되면 마는 것이다. 코드보면 이해될 것이다.

 

* 소스 코드 *

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
 
using namespace std;
using pii = pair<int, int>;
 
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
 
int map[10][10];
int n, m;
 
// visited는 단순히 섬에 번호를 매길 때 dfs를 하기 위함
bool visited[10][10];
 
// 섬들이 이어졌는지 dfs를 할 때 일종의 visit 배열임
bool check[7] = { false, };
 
// islands 번호에 해당하는 벡터에 좌표가 전부 들어가 있음
vector<pii> islands[7];
 
// graph는 인접 리스트로 섬들의 연결 상태를 나타내며, connected는 인접 행렬로 직접적인 연결 상태를 나타냄
vector<int> graph[7];
bool connected[7][7];
 
// numbering은 섬 번호 매길 때 씀
int numbering, ans = 100000;
 
// dfs는 섬 번호를 매기기 위함
void dfs(int y, int x, int numbering) {
    for (int dir = 0; dir < 4; dir++) {
        int ny = y + dy[dir], nx = x + dx[dir];
        if (ny < 0 || ny >= n || nx < 0 || nx >= m || !map[ny][nx]) {
            continue;
        }
        if (visited[ny][nx] && map[ny][nx]) continue;
 
        visited[ny][nx] = true;
        map[ny][nx] = numbering;
        islands[numbering].emplace_back(ny, nx);
        dfs(ny, nx, numbering);
    }
}
 
// 섬들이 연결되었는지 판별
void checkDfs(int cur, int& cnt) {
    for (int next : graph[cur]) {
        if (!check[next]) {
            check[next] = true;
            cnt++;
            checkDfs(next, cnt);
        }
    }
}
 
void solve(int idx, int bridge, int map[][10]) {
    // adj는 1번 섬부터 checkDfs로 탐색가능한 섬 개수
    int adj = 1;
    memset(check, 0, sizeof(check));
    check[1] = true;
    checkDfs(1, adj);
    // 1번 섬으로부터 전부 탐색 가능하면 답 갱신
    if (adj == numbering) {
        ans = min(ans, bridge);
        return;
    }
 
    // 모든 섬에 대해 탐색
    for (int i = idx + 1; i <= numbering; i++) {
        // 각 섬의 땅에 대해서 하나 씩 뽑아서 네 방향 탐색
        for (auto& cand : islands[i]) {
            int y = cand.first, x = cand.second;
            for (int dir = 0; dir < 4; dir++) {
                // 다음 칸과 다다음 칸에 다리를 놓을 수 없으면 탐색 안함
                int ny = y + dy[dir], nx = x + dx[dir];
                int nny = ny + dy[dir], nnx = nx + dx[dir];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m || map[ny][nx] == i) continue;
                if (nny < 0 || nny >= n || nnx < 0 || nnx >= m || map[nny][nnx] == i) continue;
                // 다음 칸 혹은 다다음 칸에 섬이 있어도 탐색 안함
                if ((0 < map[ny][nx] && map[ny][nx] < 9) || 0 < map[nny][nnx] && map[nny][nnx] < 9) continue;
 
                // count는 현재 점에서 놓는 다리 개수
                int count = 0;
 
                // fail은 다리를 놓을 수 있는지 없는지
                bool fail = false;
 
                // map 보존을 위해
                int temp[10][10];
                memcpy(temp, map, sizeof(temp));
 
                // opposite는 다리를 놓을 수 있을 때 다리가 놓여진 상대 섬
                int opposite;
                while (true) {
                    // ny, nx 부터 다리 놓음
                    temp[ny][nx] = 9;
                    count++;
                    int temp_y = ny + dy[dir], temp_x = nx + dx[dir];
 
                    // 바다 벗어나거나, 본인 섬에 닿으면 실패
                    if (temp_y < 0 || temp_y >= n || temp_x < 0 || temp_x >= m || map[temp_y][temp_x] == i) {
                        fail = true;
                        break;
                    }
                    // 본인 섬이 아니고 다른 섬에 다다랐으면 성공
                    if (map[temp_y][temp_x] != i && 0 < map[temp_y][temp_x] && map[temp_y][temp_x] < 9) {
                        opposite = map[temp_y][temp_x];
                        break;
                    }
                    ny = temp_y;
                    nx = temp_x;
                }
 
                // 다리 놓을 수 있을 때
                if (!fail) {
                    // 연결 안되어 있으면 연결
                    if (!connected[i][opposite]) {
                        connected[i][opposite] = true;
                        connected[opposite][i] = true;
                        graph[i].push_back(opposite);
                        graph[opposite].push_back(i);
                        solve(i, bridge + count, temp);
                        graph[i].pop_back();
                        graph[opposite].pop_back();
                        connected[i][opposite] = false;
                        connected[opposite][i] = false;
                    }
                }
            }
        }
    }
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    // 인접한 섬들 번호 매김
    numbering = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] && !visited[i][j]) {
                map[i][j] = numbering;
                visited[i][j] = true;
                islands[numbering].emplace_back(i, j);
                dfs(i, j, numbering);
                numbering++;
            }
        }
    }
    numbering--;
    solve(0, 0, map);
    if (ans == 100000) ans = -1;
    cout << ans;
}

 

 

끗.