sukwoo0711   4년 전

한번씩만봐주세요 ㅠㅠ

일단 구현하고자 한 알고리즘은


#을 발견하면 주변을 둘러봐서 . 혹은 ! 일시 bfs시작

!를 만나면 90도,180도,그냥 진행 하는 3가지 경우를 큐에 집어넣고 돌렸습니다


어디에서 문제가 발생하는걸까요??

kdk8361   4년 전

시작지점에서 출발할 때 check으로 체크를 하셨는데요. 상하좌우 순으로 검사를 하시는데 먼저 검사한 방향에서 .또는 !가 발견되었지만 다른문까지 가지 못하고 다른방향을 통해서만 갈 수 있다고 하면 결과가 안나오네요.

5
***#!
*.*..
*!.*.
*!..!
*#***

하면 3이 나와야 하는데 0이 나와요.

문제를 보니 항상 가장자리가 벽으로 이루어져있다는 정보는 없어서요.

sukwoo0711   4년 전

@kdk8361

말씀해주신 사항 고려했는데도 예외가 있나봐요 ㅠ.ㅠ

이번엔 무조건 상하좌우 4방향을 *이아닌 상태일 시 체크하게끔 만들어봤는데

그래도 어딘가에서 오류가 있나보네요..

알고리즘 접근 자체가 잘못된걸까요??

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
char map[51][51];
/*
	0
2		3
	1
*/
int visit[51][51][51];
using namespace std;
struct pos{
	int x;
	int y;
	int dir;
	int cnt;
	pos(int a,int b,int c,int d):x(a),y(b),dir(c),cnt(d){};
};
int n;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int reverse(int dir)
{
	if(dir==1)
		return 0;
	if(dir==0)
		return 1;
	if(dir==2)
		return 3;
	if(dir==3)
		return 2;
}
int bfs(int sx,int sy,int dir,int cnt)
{
	int answer =10000;
	//printf("%d %d %d %d",sx,sy,dir,cnt);
	queue <pos> q;
	q.push(pos(sx,sy,dir,cnt));
	visit[sx][sy][dir] = 1;
	while(!q.empty())
	{
		int px = q.front().x;
		int py = q.front().y;
		int dir = q.front().dir;
		int count = q.front().cnt; q.pop();	
		int nx = px+dx[dir]; int ny = py+dy[dir];
//		printf("nx %d ny %d dir %d count%d\n",nx,ny,dir,count);
		if(nx>=0 && nx<n && ny>=0 && ny<n)
		{
			if(map[nx][ny]=='*')
				continue;
			if(map[nx][ny]=='.'&&visit[nx][ny][dir]==0)
			{
				q.push(pos(nx,ny,dir,count));
				visit[nx][ny][dir] = 1;
			}
			if(map[nx][ny]=='!'&&visit[nx][ny][dir]==0)
			{
				
				visit[nx][ny][dir] = 1;
				visit[nx][ny][3-dir] = 1;
				visit[nx][ny][3-reverse(dir)]=1;						q.push(pos(nx,ny,3-dir,count+1));
				q.push(pos(nx,ny,3-reverse(dir),count+1));
				q.push(pos(nx,ny,dir,count));
			}
			if(map[nx][ny]=='#')
			{
				answer = count;
				break;
			}
		}
	}
	return answer;
}
int check(int x,int y,int dir)
{
	int i = dir;
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(map[nx][ny]!='*')
			return i;
	return -1;
}
int _min(int a,int b)
{
	if(a>b)
		return b;
	else
		return a;
}
int main()
{
	int result = 10000;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%s",&map[i]);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(map[i][j]=='#')
			{
				for(int k=0;k<4;k++){
				int pos = check(i,j,k);
				if(pos==-1)
					continue;
				else{
					result = _min(bfs(i,j,pos,0),result);
				}
				}
			}
	if(result == 10000)
		printf("0\n");
	else
		printf("%d\n",result);
}


kdk8361   4년 전

체크 순서대로 큐에 들어가서 한꺼번에 bfs로 돌아가는게 아니고 각각의 방향에서 bfs를 진행하는 방식이고 그런 방식이라면 매번 visited를 초기화 해서 각각의 방법에서 나온 최소값의 최소값을 출력해야 하지만 visited를 초기화 하지 않는게 문제인 것 같습니다.

8
****!.#!
*...!..!
*.......
#......!
*......*
*......*
*......*
********

의 경우 2가 나와야 하지만 4가 나오네요.

상하좌우 순에서 왼쪽을 먼저 검사하게 되고 그러면 1,7,↓의 visited가 true라서

우측방향에서 시작하는 bfs가 제대로 수행되지 않습니다.

sukwoo0711   4년 전

@kdk8361


감사합니다 ㅎㅎ 맞았습니다 떴네요.

결국 간과한게 

1. 탈출구를 만났을때 바로 탈출하는 경우, 그 경우가 최소한의 거울을 거친 후라는 보장이 없다.

2.한쪽 BFS를 시작해서 #을 만난경우일지라도, 다른방향의 BFS는 필요하다.


란 거였네요 ㅠ.ㅠ

정말 감사합니다 소스 읽어봐주시고.. 복 많이받으세요!

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