글 읽기 - 아 진짜 성질났는데 갑자기 풀려서 기분 좋아서 글 남깁니다.

tndyd0706 2년 전 0

시간초과 계속 나와서 질문에서 나온 것들 참고해서 고쳤습니다.

1. 3번 이상이면 그냥 -1 출력하셈

2. visit 같은거 쓰지마셈

3. 중복 안되게 하셈

4. 자기 위치 갈 수 있는지 확인할 때 하나라도 안되면 바로 안되는 걸로 하셈

고치니까 1%에서 9%로 늘었습니다.

여기서 참 화가 많이 났었는데 코드 순서 바꾸고 갑자기 해결되어 참고하시라고 올려봅니다. (속도는 1500ms긴 합니다)

54번째 줄과 60번째 줄 순서를 바꿔서 해결했습니다.

사다리 놓을 수 있는 후보들을 쭉 보면서 그 후보들마다 거기에 설치하는 경우와 그렇지 않은 경우를 나눠서 dfs를 돌렸습니다.

#include <bits/stdc++.h>
#define MAX 32
#define INF 987654321
#define pii pair<int,int>
#define endl '\n'
#define ll long long
#define FASTMODE ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int n,m,h;
//adj[a][b] : b번 세로줄과 b+1번 세로줄을 a번 점선 위치에서 연결함
bool adj[31][11];
//줄을 그을 수 있는 후보의 위치
vector<pii> hubo;
int ans=INF;
//끝났는지 확인
bool isEnd(){
	//i번째 세로줄부터 테스트 해보자
	for(int i=0;i<n;i++){
		//(y,x)는 현 위치
		int x=i;
		for(int y=0;y<h;y++){
			//오른쪽으로 가는 길이 있으면
			if(x+1<n && adj[y][x]){
				x++;
			}
			//왼쪽으로 가는 길이 있으면
			else if(x-1>=0 && adj[y][x-1]){
				x--;
			}
		}
		
		if(x!=i) return 0;
	}
	return 1;
}

void dfs(int cmp,int start){
	if(cmp>3){
		return;
	}
	if(start>=hubo.size()){
		if(isEnd()){
		ans=min(ans,cmp);
			return;
		}
		return;
	}
	
	int y=hubo[start].first;
	int x=hubo[start].second;
	
	//놓을 수 있으면 놓고 dfs 돌리기
	if(x-1<0 || adj[y][x-1]==0){
		adj[y][x]=1;
		dfs(cmp+1,start+1);
		adj[y][x]=0;
	}
	//그냥 안 놓고 다음으로 ㄱㄱ
	dfs(cmp,start+1);
	
}

int main()
{
	FASTMODE;
	cin>>n>>m>>h;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		adj[a-1][b-1]=1;
	}
	
	for(int i=0;i<h;i++)
		for(int j=0;j<n-1;j++){
			if(!adj[i][j]) hubo.push_back({i,j});
		}
	dfs(0,0);
	if(ans==INF) cout<<-1;
	else cout<<ans;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아 진짜 성질났는데 갑자기 풀려서 기분 좋아서 글 남깁니다.

tndyd0706 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말