글 읽기 - 이게 왜틀리죠??ㅠㅠㅠㅠㅠㅠ

sukwoo0711 7년 전 0

배열 X,Y가 헷갈려서 틀리는건지... 아니면 알고리즘 자체가 틀린건지;;;;;;

푼 방식은

1.시작지점(0.0)을 큐에 최초로 ENQUEUE

2.시작지점과 인접한 배열 중, 값이 1(탐색가능) 과 VISIT=0인 부분을 큐에 삽입

3. VISIT[다음X][다음Y] = VISIT[지금X][지금Y]+1 로 퍼트림

예제랑 어지간한 케이스는 맞는데.. 왜 틀리는걸:가요 ㅠㅠ

/*
	4 6
	110110
	110110
	111111
	111101


10 8
1110011111
0011110101
0000011111
0000000001
1111111111
1011000000
1111111111
0001111111

	*/

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


	typedef struct n {
		int x;
		int y;
	}q;
	q queue[2500];
	
	int front, rear, top;
	int N, M, i, j;

	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;
	}
	
	int isQueEmpty()
	{
		if (front == rear)
			return 0;
		else
			return 1;
	}
	int vectX[4] = { 0,1,0,-1 };
	int vectY[4] = { 1,0,-1,0 };

	int count = 0;
	
	void printVisit()
	{
		for (i = 0; i < 7; i++)
		{
			for (j = 0; j < 7; j++)
			{
				printf("[%d]", visit[i][j]);
			}
			puts("");
		}
	}
	void bfs()
	{
		int nextX, nextY,x,y;
	
		while(isQueEmpty()){
		
			q t = deque();
			x = t.x;
			y = t.y;


			for (i = 0; i < 4; i++)
			{
				nextX = x + vectX[i];
				nextY = y + vectY[i];
				if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N)
				{
					if (map[nextX][nextY] == 1&& visit[nextX][nextY]==0)
					{
						visit[nextX][nextY] = visit[x][y] + 1;
						enque(nextX, nextY);
					}
				}
			}
		}
	}
	int main()
	{
		scanf("%d %d",&M,&N);	//4,6
		for (i = 0; i < M; i++)	//4
			for (j = 0; j < N; j++)	//6
			{
				scanf("%1d", &map[i][j]);
			}

		enque(0, 0);
		visit[0][0] = 1;
		bfs();
		//printVisit();
		//printf("%d", visit[N - 1][M - 1]);
		printf("%d", visit[M - 1][N - 1]);

		return 0;
	}

sukwoo0711 7년 전 0

큐의 크기가 너무 작은게 원인이었습니다!!!

ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ이거에 이틀을 투자하다니

adfsfsf 5년 전 0

두 번째 예시는 10 8이 아니라 8 10인 것 같습니다.

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

문제

문제

출처

ICPC

이게 왜틀리죠??ㅠㅠㅠㅠㅠㅠ

sukwoo0711 7년 전 0

sukwoo0711 7년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말