백준(boj) 15684_사다리 조작 (파이썬, c++)

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

풀이

---

세로선과 가로선이 그려져 있는 사다리가 주어진다. 이 사다리에 선을 추가하여 출발지점과 도착지점이 모두 같아지게 하는 최소의 선 개수를 구하는 문제이다. solve() 함수를 가지고 완전 탐색 한다. 이때 출발지점과 도착지점이 모두 같은지는 check() 함수를 이용해서 검사해준다.

python3(pypy로 제출)

from sys import*
input = stdin.readline
def check():
    for i in range(m):
        s = i        #i가 시작 사다리 위치, s가 현재 사다리 위치
        for j in range(n):
            if a[j][s]: s+=1                    #사다리 표시되어있으면 오른쪽으로
            elif s-1 >=0 and a[j][s-1]: s-=1    #왼쪽이 표시되어 있으면 왼쪽으로
        if s != i: return 0
    return 1
def solve(cnt, x, y):
    res = INF
    if check(): return cnt
    if cnt == 3: return res       #3개 고른 사다리 확인 했으면 더 볼 필요 없음
    for i in range(x, n):        #완탐
        temp = y if x==i else 0
        for j in range(temp, m-1):
            if a[i][j]:
                j+=1
            else:
                a[i][j]=1        #사다리 표시
                res = min(res, solve(cnt+1, i, j+2))
                a[i][j]=0        #사다리 표시 제거
    return res
​
INF = 1e9
m,k,n = map(int,input().split())
a=[[0]*m for _ in range(n)]
for i in range(k):
    x, y = map(int,input().split())
    a[x-1][y-1] = 1
ans=solve(0,0,0)
print(ans if ans != INF else -1)    #결과가 INF면 3개 이하 없는거, -1 출력

C++

#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 1e9;
int m,k,n;
int a[30][10];
bool check()
{
    for(int i=0; i<m; i++)
    {
        int s = i;
        for(int j=0; j<n; j++)
        {
            if(a[j][s]) s+=1;
            else if(s-1 >= 0 && a[j][s-1]) s-=1;
        }
        if(s != i) return 0;
    }
    return 1;
}
int solve(int cnt, int x, int y)
{
    int res = INF;
    if(check()) return cnt;
    if(cnt == 3) return res;
    for(int i=x; i<n; i++)
    {
        int temp = (x==i ? y : 0);
        for(int j=temp; j<m-1; j++)
        {
            if(a[i][j]) j+=1;
            else
            {
                a[i][j] = 1;
                res = min(res, solve(cnt+1, i, j+2));
                a[i][j]=0;
            }
        }
    }
    return res;
}
​
int main()
{
    scanf("%d %d %d", &m, &k, &n);
    for(int i=0; i<k; i++)
    {
        int x,y;
        scanf("%d %d", &x, &y);
        a[x-1][y-1] = 1;
    }
    int ans = solve(0,0,0);
    printf("%d", ans != INF ? ans : -1);
    return 0;
}

고찰

---

처음에 solve() 함수에 cnt 인자 하나만 가지고 (n) * (m-1) 연산을 반복하다보니 불필요한 연산이 많아져서 시간초과가 났었다.