[BOJ/백준][Gold5] 17622 : 타일 교체 (C++)

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

17622번: 타일 교체

 

 

[난이도] Gold5
[유형] DFS

[풀이]
N이 50이고 k가 1일 때,
k를 사용해서 모든 타일을 6개의 모양으로 바꿔보고 dfs를 하는 방식의 브루트포스로 풀게 되면
O(50*50*6*50*50) 으로 시간초과가 발생할 것으로 생각되지만
dfs를 이용해 실제 경로 탐색을 할 때 각 타일에서 갈 수 있는 다음 타일은 한개밖에 없기 때문에 많은 경로가
가지치기 될 것으로 기대되어 실제로 O(50*50) 만큼의 시간이 발생하지 않습니다.

그러므로 모든 타일을 바꿔는 브루트포스 방식으로 문제 해결이 가능합니다.

 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dy[4]={-1,0,1,0},dx[4]={0,-1,0,1};
int line[6][4]={{0,0,1,1},{0,1,1,0},{1,0,0,1},{1,1,0,0},{1,0,1,0},{0,1,0,1}};
int N,k,board[52][52],visit[52][52];
int match(int i){
    if(i<2) return i+2;
    return i-2;
}
int dfs(int y,int x){
    if(y==N-1&&x==N-1){
        if(board[y][x]==2||board[y][x]==5) return 1;
        return -1;
    }
    if(y==0&&x==0){
        if(board[y][x]%2==0) return -1;
    }
    visit[y][x]=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        int m = match(i);
        if(ny<0||nx<0||ny>=N||nx>=N||!line[board[y][x]][i]||!line[board[ny][nx]][m]||visit[ny][nx]) continue;
        int ret = dfs(ny,nx);
        if(ret==-1) return -1;
        return ret+1;
    }
    return -1;
}
int main(){
    scanf("%d%d",&N,&k);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&board[i][j]);
        }
    }
    int ans=9e8;
    if(k){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int t = board[i][j];
                for(int k=0;k<6;k++){
                    if(t!=k) {
                        board[i][j]=k;
                        memset(visit,0,sizeof(visit));
                        int ret = dfs(0,0);
                        if(ret!=-1) ans=min(ans,ret);
                    }
                }
                board[i][j]=t;
            }
        }       
    }else ans=dfs(0,0);
    printf("%d",ans == 9e8 ? -1 : ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17622.cpp