글 읽기 - 시간초과 질문드립니다.

lswoo3021 5년 전 1

게시판에 올려주신 테스트케이스 모두 정답으로 나옵니다.

그리고, 코드상으로 봤을때... bfs와 dfs 백트래킹 이용해서 중복되는 건 없어보이는데

시간초과가 나오네요 ..

9%에서 항상 딱걸려가지고 몇초 멈춘다음에 시간초과로 뜹니다..

혹시 조언해주실 분 있다면 부탁드립니다 !

#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>

#define MAP_SIZE 11

using namespace std;
char map[MAP_SIZE][MAP_SIZE];
int n, m;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
pair <int, int> r, b, o;
int ans = 2147483647;
int visit[10][10][10][10];

typedef struct state {
	pair<int, int> point; int fall = 0;   // r이 구멍에 빠지면 1 b가 빠지면 2 빠진것 없으면 0
}state;

state bfs(pair<int, int> s, int rb, int dir) {
	int x, y, nx, ny;
	state ret;
	queue <pair<int, int>> q;
	q.push({ s.first, s.second });
	while (!q.empty()) {
		x = q.front().first; y = q.front().second;
		q.pop();
		nx = x + dx[dir]; ny = y + dy[dir];   // dir 방향으로만 이동
		if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
		if (map[nx][ny] == 'O') {   // 구멍으로 들어가는 경우
			ret = { {nx, ny}, rb };
			return ret;
		}
		if (map[nx][ny] == '.') {
			q.push({ nx, ny });
		}
	}
	ret = { {x, y}, 0 };
	return ret;
}



void dfs(pair<int, int> rr, pair<int, int> bb, int d) {
	state sr, sb;
	
	for (int i = 0; i < 4; i++) { // 좌, 우, 상, 하
		sr = bfs(rr, 1, i);   // 빨간공
		sb = bfs(bb, 2, i);   // 파란공
		if (sr.point == sb.point) {   // 공이 겹치는 경우 위치보정
			if (i == 0) {
				rr.second < bb.second ? sb.point.second++ : sr.point.second++;
			}
			if (i == 1) {
				rr.second < bb.second ? sr.point.second-- : sb.point.second--;
			}
			if (i == 2) {
				rr.first < bb.first ? sb.point.first++ : sr.point.first++;
			}
			if (i == 3) {
				rr.first < bb.first ? sr.point.first-- : sb.point.first--;
			}
		}
		if (d >= ans) return;
		if (sr.fall == 1 && sb.fall != 2) {   // 성공한 경우
			ans = min(ans, d);
			return;
		}
		if (sb.fall == 2) {   //실패한 경우
			continue;
		}
		if ((sr.point.first == rr.first && sr.point.second == rr.second) &&
			(sb.point.first == bb.first && sb.point.second == bb.second)) {
			// 더 이상 움직이지 못하는 경우
			//cout << "같은 동작" << endl;
			continue;
		}
		if (visit[sr.point.first][sr.point.second][sb.point.first][sb.point.second]){
			continue;
		}
		visit[sr.point.first][sr.point.second][sb.point.first][sb.point.second] = 1;
		dfs({ sr.point.first, sr.point.second }, { sb.point.first, sb.point.second }, d + 1);
		visit[sr.point.first][sr.point.second][sb.point.first][sb.point.second] = 0; // backtracking
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {   // input
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'O') o = { i, j };
			if (map[i][j] == 'R') r = { i, j };
			if (map[i][j] == 'B') b = { i, j };
			if (map[i][j] == 'R' || map[i][j] == 'B') map[i][j] = '.';
		}
	}
	vector <int> v;
	visit[r.first][r.second][b.first][b.second] = 1;
	dfs(r, b, 1);
	if (ans > 10) cout << -1 << endl;
	else cout << ans << endl;


	int wait = 0;
	cin >> wait;



	return 0;
}

lswoo3021 5년 전 0

죄송합니다.. 아마추어같이 깊이가 10이상 되는 경우를 빼먹었네요 ..

65번째 라인에

if (d > 10) return;

이문장 추가해서 정답나왔습니다~

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

lswoo3021 5년 전 1

lswoo3021 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말