글 읽기 - 무엇이 틀렸을까요..

hioo 4년 전 0

제가 놓친 테스트케이스가 무엇일까요

왜 자꾸 틀렸습니다가 나올까요

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct position
{
	int n;
	int m;
};

int N, M; // 그래프 사이트 (NxM)
int graph[100][100];
int dist[100][100]; // (0,0)에서 각 위치까지의 최단 거리를 나타내는 배열

struct position queue[10000];
int front, rear;

void enqueue(int n, int m)
{
	// queue가 꽉 찬 경우
	if ((rear + 1) % 10000 == front)
	{
		return;
	}

	queue[rear].n = n;
	queue[rear].m = m;
	rear = (rear + 1) % 10000;

	return;
}

struct position dequeue()
{
	struct position temp;
	// queue가 빈 경우
	if (rear == front)
	{
		temp.n = -999;
		temp.m = -999;
		return temp;
	}

	temp.n = queue[front].n;
	temp.m = queue[front].m;
	front = (front + 1) % 10000;
	return temp;

}

// queue에 (n,m) 좌표가 있으면 1, 없으면 0 반환
int isInQueue(int n, int m)
{
	int a = front;
	int b = rear;

	while (1)
	{
		if (queue[a].n == n && queue[a].m == m)
		{
			return 1;
		}
		a = (a + 1) % 10000;

		if (a == b)
		{
			return 0;
		}
	}
}

// 최단거리 계산하는 함수
void doBFS(int n, int m)
{
	enqueue(n, m);
	dist[n][m] = 1; // cnt 초기값 1. (0,0) 위치의 거리는 1.

	while (1)
	{
		struct position cur = dequeue();

		// dequeue 했더니 queue에 남아있는 좌표가 없는 경우
		// 모두 끝난 경우
		if (cur.n == -999 && cur.m == -999)
		{
			return;
		}

		// graph 값이 1이고, queue에 없고, dist가 0이면
		
		// 상
		if (graph[cur.n - 1][cur.m] == 1 && isInQueue(cur.n - 1, cur.m) == 0 && dist[cur.n - 1][cur.m] == 0)
		{
			enqueue(cur.n - 1, cur.m);
			dist[cur.n - 1][cur.m] = dist[cur.n][cur.m] + 1;

		}
		// 하
		if (graph[cur.n + 1][cur.m] == 1 && isInQueue(cur.n + 1, cur.m) == 0 && dist[cur.n + 1][cur.m] == 0)
		{
			enqueue(cur.n + 1, cur.m);
			dist[cur.n + 1][cur.m] = dist[cur.n][cur.m] + 1;

		}

		// 좌
		if (graph[cur.n][cur.m - 1] == 1 && isInQueue(cur.n, cur.m - 1) == 0 && dist[cur.n][cur.m - 1] == 0)
		{
			enqueue(cur.n, cur.m - 1);
			dist[cur.n][cur.m - 1] = dist[cur.n][cur.m] + 1; 
		}

		// 우
		if (graph[cur.n][cur.m + 1] == 1 && isInQueue(cur.n, cur.m + 1) == 0 && dist[cur.n][cur.m + 1] == 0)
		{
			enqueue(cur.n, cur.m + 1);
			dist[cur.n][cur.m + 1] = dist[cur.n][cur.m] + 1;
		}
		
		
	}
}

int main(void)
{
	// 그래프 사이즈 입력받기
	scanf("%d %d", &N, &M);


	// graph 배열에 하나씩 입력받기 (1 or 0)
	// 1이면 이동 가능한 위치, 0이면 이동 불가능 한 위치
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%1d", &graph[i][j]);
		}
	}

	doBFS(0, 0);

	printf("%d", dist[N-1][M-1]);
	return 0;	

}

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

문제

문제

출처

ICPC

무엇이 틀렸을까요..

hioo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말