안녕하세요. 코딩도치 입니다~
오늘은 백준 알고리즘 15684번 사다리 조작 문제를 풀어보려고 합니다!
이해하는 것도, 방법을 생각하기도, 구현하기도 참 어려운 문제입니다ㅜㅜ 그래도 한번 차근차근 알아보겠습니다!
먼저 이 문제는 기본적으로 dfs를 활용해서 모든 경우의 수를 다 생각해보고 판단할 수 있습니다.
하지만 이렇게 하면 시간초과가 나버리는데요.
그렇다고 무슨 특별한 방법이 있는 것은 아닙니다.
모든 경우의 수를 본다는 전제를 두고 그 경우의 수를 줄여주는 방법 밖에는 없습니다.
그럼 경우의 수는 어떻게 줄일까요??
간단합니다. 기본적인 dfs방식에서 어떠한 조건을 주고 해당 조건을 만족하는 경우에만 이어서 탐색을 하도록 하는 것이죠.
이러한 방법을 백트래킹(Backtracking)이라고 합니다.
결국 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것입니다.
이 백트래킹은 어떤 정해진 형태가 없습니다.
문제마다 조건이 다르고, 그에 따라 구현방식이 달라지기 때문입니다.
그래서 이러한 문제를 만났을 때 가장 중요한 것은 문제를 정확히 이해하고 종료 조건을 찾아내는 것입니다.
문제에 따라서 정말 어려울 수도, 쉬울 수도 있는 것이죠.
사다리 조작 문제 또한 문제를 이해하고 종료 조건을 찾아내는 것에 많은 어려움을 겪는 문제입니다.
그럼 본격적으로 사다리 조작 문제를 풀어보겠습니다.
저는 사다리를 이차원 배열로 표현하였습니다.
처음에는 사다리를 어떻게 이차원 배열로 표현할까 고민을 많이 하였고, 다음과 같은 방법으로 표현하였습니다.
- 세로선 사이의 연결이 없다면 0
- 왼쪽 세로선과 연결이 되어 있다면 1
- 오른쪽 세로선과 연결되어 있다면 2
그리고 dfs를 기본으로 하여 문제를 해결하였습니다.
제가 푼 방식은 다음과 같습니다.
놓을 수 있는 최대 다리의 개수는 3개이고, 시작과 끝을 같게 만들기 위해 필요한 최소 다리의 개수를 파악하는 것이기 때문에
0개의 다리를 놓는 경우부터 3개의 다리를 놓는 경우까지만 탐색을 하도록 하였습니다.
traver 함수에 들어가게 되면
- 가장 먼저 finish 변수 값을 확인하게 됩니다.
finish변수는 시작과 끝이 같이 지는 경우를 만났을 때 1로 바뀌게 됩니다.
finish변수가 1이라면 그 이후로는 더이상 탐색을 하지 않아도 되기 때문에 dfs의 종료조건입니다.
왜냐하면 시작과 끝을 같게 만드는 데 필요한 다리 개수의 최소값을 찾는 것이고,
놓는 다리의 개수를 0개부터 하나씩 증가시켜가면서 탐색하기 때문에
진행 중에 시작과 끝을 같게 만드는 경우가 발생한다면 그 순간이 다리 개수의 최소값이 되는 것입니다.
따라서 이후로는 탐색을 진행하지 않아도 되는 것입니다.
- 다음으로 '놓기를 원하는 다리 개수'와 '실제로 놓아진 다리 개수'가 같은지 확인합니다.
놓기를 원하는 다리 개수와 실제로 놓아진 다리 개수가 같아졌을 때가 바로 시작과 끝이 같은지 검사 해야하는 순간이기 때문입니다.
0개를 놓기를 원하면 0개의 다리가 추가로 놓아졌을 때 시작과 끝이 같은지 확인하고
1개를 놓기를 원하면 1개의 다리가 추가로 놓아졌을 때 시작과 끝이 같은지 확인하는 것입니다.
이때 시작과 끝이 같지 않은 경우가 한번이라도 발생한다면 더이상 검사를 진행하지 않아도 됩니다.
모든 세로선의 시작과 끝이 같아야 하기 때문입니다.
그래서 만약에 모든 세로선의 시작과 끝이 같다면 finish를 1로 만들어 더이상 검사를 진행하지 않아도 된다고 알려주는 것입니다.
- 만약 위의 두 조건문에 모두 해당하지 않는다면 다리를 놓아줘야하는 경우입니다.
이때 다리를 놓고 재귀함수로 다시 traver함수로 들어가게 되는데,
여기서 중요한 것은 다시 사다리를 처음부터 탐색하게 되면 시간 초과가 발생한다는 것입니다.
따라서 사다리의 처음부터 검사하는 것이 아니라,
방금 다리를 놓은 순간부터 이어서 검사할 수 있도록 값을 넘겨주는 것이 핵심입니다.
해당 다리는 놓아보고 검사가 끝났다면 그 다리는 다시 없애줘야 합니다.
다음 다리를 놓고 검사해 보아야 하기 때문입니다.
아래는 소스코드입니다.
#include <iostream>
using namespace std;
/******
row : 시작 행
column : 시작 열
add_Edge_Count : 추가로 놓아진 다리 개수
******/
void traver(int row, int column, int add_Edge_Count);
int result = 0; // 놓는 다리의 개수
int N, M, H;
int finish = 0; // 더이상 검사를 진행할 필요가 없을 때 : 1
int map[31][11] = {0};
int main(){
int a, b;
scanf("%d %d %d", &N, &M, &H);
for(int i=0; i<M; i++){
scanf("%d %d", &a, &b);
// 연결된 선이 없으면 : 0
// 왼쪽으로 연결된 선이 있으면 : 1
// 오른쪽으로 연결된 선이 있으면 : 2
// 연결이 되면 각 세로선 입장에서 한쪽은 왼쪽으로, 한쪽은 오른쪽으로 연결되기 때문에
map[a][b] = 1;
map[a][b+1] = 2;
}
// 놓을 수 있는 다리의 개수가 최대 3개이므로
for(int i=0;i<=3;i++){
result = i;
traver(1,1,0);
if(finish == 1){
printf("%d\n", result);
return 0;
}
}
printf("-1\n");
return 0;
}
void traver(int row, int column, int add_Edge_Count){
if(finish == 1){
return;
}
// 원하는 만큼 추가로 다리가 놓아진 경우
// (result: 놓길 원하는 다리 개수, add_Edge_Count: 추가로 놓아진 다리 개수)
if(result == add_Edge_Count){
int check = 0;
// 간선 타고 가면서 시작과 끝 검사(시작과 끝이 같아야 함)
for(int i=1; i<=N; i++){
int start = i;
for(int j=1; j<=H; j++){
if(map[j][start] == 1){
start++;
}else if(map[j][start] == 2){
start--;
}
}
// 시작과 끝이 같지 않은 경우가 한번이라도 있다면 검사 중지
if(start != i){
check = 1;
break;
}
}
// 모든 시작과 끝이 같다면 finish를 1로 만듬 - 이후로 검사할 필요없음
if(check == 0){
finish = 1;
}
return ;
}
// 다리 놓기
for(int i = row; i<=H; i++){
for(int j = column; j< N; j++){
if(map[i][j] == 0 && map[i][j+1] == 0){
// j와 j+1 사이에 놓아진 다리가 없다면 다리 추가
map[i][j] = 1;
map[i][j+1] = 2;
if(j+2 < N){
// 정해진 세로선의 개수를 넘어 가지 않으면
traver(i, j+1, add_Edge_Count + 1);
}else{
// 넘어가면 가로선을 하나 증가시킴
traver(i+1, 1, add_Edge_Count + 1);
}
// 검사가 끝나면 다음 검사를 위해 다시 놓았던 다리는 없애줘야함
map[i][j] = 0;
map[i][j+1] = 0;
}
}
}
}감사합니다.
'알고리즘 > [Beakjoon]백준' 카테고리의 다른 글
| 1. [C++]백준 알고리즘 1260번: DFS와 BFS - 코딩도치 (1) | 2019.11.11 |
|---|