글 읽기 - 사다리조작 시간초과 걸리는코드/패스한코드 차이점을 잘 모르겠습니다.

colorxxx 5년 전 1

이 문제의 경우 모든 경우의 수가 300C3이여서 완전탐색을 돌렸더니 시간초과가 났습니다.

그래서 다른 코드를참조해보니 똑같이 완전탐색을 했는데도 시간초과안에 패스했더군요

저의 코드와 패스한코드의 차이점은 main함수에서 dfs(1)을 돌렸는지의 유무입니다.

dfs를 돌릴때 항상 0에서 시작한다던지의 초반 출발에 대한 제약사항이 없으면 모든 인덱스가 출발지점이 될 수 있으므로

main 함수 안에서 항상 저러한 방식으로 출발인덱스를 지정해주고 리셋하고 다시 시작하는 경우의 코드를 항상 진행해왔었는데

for (int i = 1; i < N; i++) {

for (int j = 1; j <= H; j++) {

if (ladder[j][i] == 0 && ladder[j][i-1] == 0 && ladder[j][i+1]==0){ ladder[j][i] = 1; dfs(i, j, 1) ladder[j][i] = 0; } } }

이 문제에선 이렇게 하니깐 틀리네요 ㅠㅠ dfs 내부함수에서 완전탐색을 진행해야 시간복잡도 안에 들어오네요

제가 궁금한것은 이것입니다.

어차피 300C3이니깐 제가 작성한 코드처럼 작성해도 시간제한안에 들어와야 하는 아닌가요?

2. 코드를 짤때 위의 코드처럼 짜시나요 아니면 아래 코드처럼 짜시나요 맨날 아래처럼 짜오다가 이 문제 시간초과

걸려서 코드 스타일 바꿔야하나 고민중입니다.. 혹시 아래처럼 짜도 시간안에 들어오신분들 어케 짜셨는지 궁금합니다

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

int n, m, h,ret;
int ans = 999999999;
int map[31][11];

bool check() {
	bool ret = true;
	for (int i = 1; i <= n; i++) {
		int pos = i;
		for (int j = 0; j <= h; j++) {
			if (map[j][pos] == 1)++pos;
			else if (map[j][pos - 1] == 1)pos--;	
		}
		if (pos != i) {return ret = false;}
	}
	return ret;
}


void dfs(int count, int y, int x) {
	if (count >= ret) return;
	if (check()) {
		ret = count;
		return;
	}
	if (count == 3) return;

	for (int i = y; i <= h; i++) {
		for (int j = x; j < n; j++) {
			if (map[i][j]==0 && map[i][j-1] == 0&& map[i][j+1] == 0) {
				map[i][j] = 1;
				dfs(count + 1, i, j+1);
				map[i][j] = 0;
			}
		}
		x = 1;
	}
}


int main() {
	scanf("%d %d %d", &n, &m, &h);
	int a, b;
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		map[a][b] = 1;
	}
	ret = 4;
	dfs(0, 1, 1);
	if (ret == 4) ret = -1;
	printf("%d", ret);
}

///////////////////////////////////시간초과 pass한코드////////////////////////


#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

int N, M, H;
int flag = 1;
int ans = 999999999;
int ladder[31][12];//[H]위치에서[N]과 [N+1]연결되어있다, [N+1]과 [N]이 연결되어있기도 함.

bool down(){//사다리 연결된대로 나온다.
	
	for (int i = 1; i <= N; i++) {

			int idx = i;
			for (int j = 1; j <= H; j++) {
				if (ladder[j][idx]) { //idx와 idx+1을 연결하는 사다리가 j열에 있을때
					idx += 1; //한칸 오른쪽으로 옮겨져긴다

				}

				else if (ladder[j][idx-1]) {
					idx -= 1; //한칸 왼쪽으로 옮겨져간다

				}
			}

			if (idx != i) {//만약 인덱스가 매칭이 안된다면
				return 0;
				break; //탐색종료
			}			
	}
	return true;
}

void dfs(int r, int c, int cnt) {
	
	
	if (down() ==true) { //만약 매칭된다면
		ans = min(ans, cnt); //가장 작은 값을 적용한다.
		return;
	}
	if (cnt == 3) {
		return;
	}
	//연결해준다

	for (int i = 1; i < N; i++) {
		for (int j = r+1; j <= H; j++) {
			if (ladder[j][i]== 0 && ladder[j][i-1] == 0&& ladder[j][i+1]== 0) {
				ladder[j][i] = 1;
				dfs(i, j, cnt + 1);//사다리를 연결
				ladder[j][i] = 0;
			}
		}
	}

}


int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; //b번 세로선과 b+1세로선을 a번 점선 위치에서 연결했다.
		ladder[a][b] = 1;//양방향 그래프로 체크한다 b-b+1/ b+1-b
		
	}
	if (down()==true) {// 완성이 된다면
		cout << 0; //0 출력
		return 0;
	}
	for (int i = 1; i < N; i++) {
		for (int j = 1; j <= H; j++) {
			if (ladder[j][i] == 0 && ladder[j][i-1] == 0 && ladder[j][i+1]==0){ //만약 사다리가 없다면
				ladder[j][i] = 1;
				dfs(i, j, 1);//사다리를 연결
				ladder[j][i] = 0;
            }
		}
	}
	
	if (ans == 999999999) cout << -1;

	else cout << ans;

}
////////////////////////////////시간초과 걸린코드/////////////////////////

upple1 5년 전 1

113번 째 줄에 항상 i가 1부터 시작하는 것 때문에 시간초과 걸린 것 같네요.

upple1 5년 전 1

수정해서 제출해 본 결과 틀렸습니다. 나오네요 다른 부분에서 실수하셨는지 체크해보세요

colorxxx 5년 전 0

아 네 수정하니깐 시간 내에 답 나오네요! 감사합니다 ㅋㅋㅋ

시간초과 났떤건 말씀해주셨던것처럼 r=1 c=1에서 중복탐색 하는거랑

틀렸던건

for문끝나고 r=1만들어주는걸 뺴먹었었네요 ㅋㅋ 감사합니다

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

문제

문제

출처

ICPC

사다리조작 시간초과 걸리는코드/패스한코드 차이점을 잘 모르겠습니다.

colorxxx 5년 전 1

upple1 5년 전 1

upple1 5년 전 1

colorxxx 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말