글 읽기 - 접근방법이 잘못된건가요??ㅠㅠ

sukwoo0711 6년 전 0

안녕하세요. 일단 제가 구현하려한 방법은

1. 모든 L지점의 좌표를 찾아서 큐에 삽입

2.큐가 빌 때까지, DEQUE해서, 해당지점을 시작점으로 깊이탐색 실시(스택 이용)

3.VISIT은 매 결과마다 MEMSET으로 초기화(미 방문상태로)

예제케이스는 맞게 돌아가는것 같은데.. 어디에서 실수한걸까요??ㅠ

너무 어렵게 생각한거같은데

#include <stdio.h>
#include <memory.h>
char map[500][500];
int visit[500][500];

int front, rear, top;
int N, M, i, j;

int vectX[4] = { 0,1,0,-1 };
int vectY[4] = { 1,0,-1,0 };

int count = 0;
int max;


typedef struct n {
	int x;
	int y;
}q;
q queue[2500];
q stack[2500];


void enque(int x, int y)
{
	q t;
	t.x = x;
	t.y = y;
	queue[rear++] = t;
}
q deque()
{
	q t = queue[front++];
	return t;
}
void push(int x, int y)
{
	q t;
	t.x = x; t.y = y;
	stack[top++] = t;
}
q pop()
{
	q t = stack[--top];
	return t;
}
int isStackEmpty()
{
	if (top == 0)
		return 0;
	else
		return 1;
}
int isQueEmpty()
{
	if (front == rear)
		return 0;
	else
		return 1;
}

void dfs(int startx,int starty)
{
	int nextX, nextY;
	visit[startx][starty] = 1;
	while (isStackEmpty())
	{
		q t = pop();
		for (i = 0; i < 4; i++)
		{
			nextX = t.x + vectX[i];
			nextY = t.y + vectY[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M)
			{
				if (map[nextX][nextY] == 'L' && visit[nextX][nextY] == 0)
				{
					visit[nextX][nextY] = visit[t.x][t.y] + 1;
					push(nextX, nextY);
					
				}
				if (visit[nextX][nextY] > max)
					max = visit[nextX][nextY];
			}
		}
	}
}
void printVisit()
{
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++) 
		{
			printf("[%d]", visit[i][j]);
		}
		puts("");
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
		scanf("%s", &map[i]);
	for(i=0;i<N;i++)
		for (j = 0; j < M; j++)
		{
			if (map[i][j] == 'L')
			{
				enque(i, j);
			}
		}
	while (isQueEmpty())
	{
		q t = deque();
		push(t.x, t.y);
		dfs(t.x, t.y);	
		//printf("start = %d %d\n", t.x, t.y);
		printVisit();
		puts("");
		memset(visit, 0, sizeof(visit) / sizeof(int));
	}
	printf("%d\n", max-1);
	
	return 0;
}

sukwoo0711 6년 전 1

4 4

LLLL

LLLL와 같은 케이스에선 BFS로 진행 시, 6이 나오게 되는데 DFS로 진행시 15가 나와서 틀렸네요..

최단거리니까 무조건 QUEUE를 이용한 BFS를 이용해야하는게 맞았습니다 ㅠㅠ

모든 배열의 L값에서 BFS를 실시하고, 최대값을 저장한 뒤, 탐색이 끝나고 최대값을 출력하는방식으로 풀어서 성공했습니당.

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

문제

문제

출처

ICPC

접근방법이 잘못된건가요??ㅠㅠ

sukwoo0711 6년 전 0

sukwoo0711 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말