[ BOJ 백준 3482번 - Labyrinth ] 해설 및 코드

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

 

목적

임의의 free block 2개를 연결했을 때, 그 길이의 최대값을 구하자.

 

접근법

1. 백준 1967번 - 트리의 지름 문제와 같은 문제라고 보면 된다.

2. 인접한 free block으로 이동할 수 있고, 임의의 free block 2개 사이에는 길이 1개만 있다는 문제의 조건에 따라, Labyrinth는 트리구조를 갖는다.

3. 모든 period를 이어서 이를 트리의 형태로 보면, 어느 지점을 트리의 노드로 보아야 하는지 명확해질 것이고, 위 문제와 동일하다는 것을 알 수 있을 것이다. 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;i++)
using namespace std;
 
const int LEN=1000;
int ans,di[]={1,-1,0,0},dj[]={0,0,1,-1};
char s[LEN][LEN];
 
int dfs(int i,int j,int k){
    int a=0,b=0,r=k+(k&1?-1:1);
    f(d,0,4)if(d!=r){
        int ni=i+di[d],nj=j+dj[d];
        if(s[ni][nj]=='#')continue;
        
        int tmp=dfs(ni,nj,d)+1;
        if(a<tmp)b=a,a=tmp;
        else if(b<tmp)b=tmp;
    }
    ans=max(ans,a+b);
    
    return a;
}
 
void sol(int c,int r){
    f(i,0,r)f(j,0,c)if(s[i][j]=='.'){
        dfs(i,j,4);
        return;
    }
}
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    int t;cin>>t;
    while(t--){
        int c,r;
        cin>>c>>r;f(i,0,r)cin>>s[i];
        ans=0;
        sol(c,r);
        cout<<"Maximum rope length is "<<ans<<".\n";
    }
    
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.