글 읽기 - 시간초과...더 이상 좋게 짤 수가 없습니다...리뷰해주시면 감사하겠습니다.

yunbinni 1년 전 0

우선 저는, DFS로 생각했습니다.

DFS함수의 인수를 y, x좌표, 로봇방향(dir), 깊이(L)로 설계했습니다.

왼쪽으로 회전할땐 dir을 1씩 줄이고 dir이 0이하면 다시 3으로 복구하여서

방향벡터의 인덱스로 쓸 생각이었습니다.

dy[4]={-1, 0, 1, 0};

dx[4]={0, 1, 0, -1};

에서 인덱스(dir)가 하나가 줄면 왼쪽으로 회전한다...이렇게요.

문제의 규칙 2a가 어떤경우든, 왼쪽으로 회전은 하니까

일단 회전부터 시켰습니다.

그래서 방문한 적이 없고, 빈 칸이면 다음 레벨(깊이)로의 재귀를 실시했습니다.

방문체크는 어차피 다음재귀 맨처음에 하니, 미리 하진 않았습니다.

제가 DFS로 짠 것때문에 시간초과가 뜬 걸까요?

#include<bits/stdc++.h>
using namespace std;

int n, m, r, c, d, res=INT_MIN;
int arr[54][54], chk[54][54];
int dy[4]={-1, 0, 1, 0};
int dx[4]={0, 1, 0, -1};

void DFS(int y, int x, int dir, int L) {
	if(L>res) res=L;
	chk[y][x]=1;
	for(int i=0; i<4; i++) {
		dir--; if(dir<0) dir=3; //회전 
		int ny=y+dy[dir]; //전진 
		int nx=x+dx[dir];
		if(ny<=0 || nx<=0 || ny>=n-1 || nx>=m-1) continue; //경계라면 skip 
		if(chk[ny][nx]==0 && arr[ny][nx]==0) {
			DFS(ny, nx, dir, L+1);
			chk[ny][nx]=0;
		}
	}
	//4방향모두 돌았을때
	int ny=y-dy[dir]; //후진 
	int nx=x-dx[dir];
	if(arr[ny][nx]==1) return;
	else DFS(ny, nx, dir, L);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	cin>>r>>c>>d;
	for(int i=0; i<n; i++) {
	for(int j=0; j<m; j++) {
		cin>>arr[i][j];
	}}
	DFS(r, c, d, 1);
	cout<<res<<"\n";
	return 0;
}

yhj1937 1년 전 2

DFS내 for문에서 여러 개의 DFS 분기가 생깁니다. 로봇 청소기가 왼쪽에 청소할 공간을 만나면 더 이상 회전할 필요가 없겠죠?

yunbinni 1년 전 3

yhj1937님 정말, 감사드립니다!

덕분에 '맞았습니다'가 떴습니다!!!!!

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

문제

문제

출처

ICPC

시간초과...더 이상 좋게 짤 수가 없습니다...리뷰해주시면 감사하겠습니다.

yunbinni 1년 전 0

yhj1937 1년 전 2

yunbinni 1년 전 3

yhj1937님 정말, 감사드립니다!

덕분에 '맞았습니다'가 떴습니다!!!!!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말