글 읽기 - 너무 어렵네요 왜 틀린지 조언좀 부탁드립니다.

acmbono 6년 전 0

작은 테스트(주어진 테스트)는 해보았으나 잘 맞은거 같은데

제출을 할 때, 틀리다고 뜹니다. 어디가 문제인지 피드백 부탁드립니다.

좋은 밤 되세요

#include <iostream>
#include <stdio.h>
using namespace std;
typedef struct pos {
	int i;
	int j;
}p;

int m, n;
int map[105][105];
int visit[105][105];
int mapCnt[105][105];
int cnt = 1;
p pQueue[300001];
int front, lear;

bool isEmpty() {
	if (front != 0 && lear != 0) {
		if (front == lear)
			return true;
		else {
			return false;
		}
	}
	else {
		return false;
	}
}

void search_BFS(int i, int j) {
	if (isEmpty())
		return;

	if (map[i + 1][j] != 0) {
		if (visit[i + 1][j] == 0) {
			pQueue[front].i = i + 1;
			pQueue[front].j = j;
			visit[i + 1][j] = 1;
			mapCnt[i + 1][j] = mapCnt[pQueue[lear].i][pQueue[lear].j] + 1;
			front++;
		}
		else {
			if (mapCnt[i + 1][j] < mapCnt[i][j])
				mapCnt[i + 1][j] = mapCnt[i][j];
		}
	}

	if (map[i][j + 1] != 0) {
		if (visit[i][j + 1] == 0) {
			pQueue[front].i = i;
			pQueue[front].j = j + 1;
			visit[i][j + 1] = 1;
			mapCnt[i][j + 1] = mapCnt[pQueue[lear].i][pQueue[lear].j] + 1;
			front++;
		}
		else {
			if (mapCnt[i][j + 1] < mapCnt[i][j])
				mapCnt[i][j + 1] = mapCnt[i][j];
		}

	}

	if (map[i - 1][j] != 0) {
		if (visit[i - 1][j] == 0) {
			pQueue[front].i = i - 1;
			pQueue[front].j = j;
			visit[i - 1][j] = 1;
			mapCnt[i - 1][j] = mapCnt[pQueue[lear].i][pQueue[lear].j] + 1;
			front++;
		}
		else {
			if (mapCnt[i - 1][j] < mapCnt[i][j])
				mapCnt[i - 1][j] = mapCnt[i][j];
		}
	}

	if (map[i][j - 1] != 0) {
		if (visit[i][j - 1] == 0) {
			pQueue[front].i = i;
			pQueue[front].j = j - 1;
			visit[i][j - 1] = 1;
			mapCnt[i][j - 1] = mapCnt[pQueue[lear].i][pQueue[lear].j] + 1;
			front++;
		}
		else {
			if (mapCnt[i][j - 1] < mapCnt[i][j])
				mapCnt[i][j - 1] = mapCnt[i][j];
		}

	}

	lear++;
	search_BFS(pQueue[lear].i, pQueue[lear].j);

}
int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &map[i][j]);
		}

	}
	visit[1][1] = 1;
	mapCnt[1][1] = 1;
	pQueue[front].i = 1;
	pQueue[front].j = 1;
	front++;
	search_BFS(1, 1);

	cout << mapCnt[n][m] << endl;
	return 0;
}

indioindio 6년 전 0

6 4

1111

1101

0101

1101

1001

1111

일 때 9 대신 10을 출력합니다.

방문 순서에 따라 값이 제대로 업데이트가 안 되는 것 같네요.

좌우대칭한 미로는 9를 제대로 출력합니다.

kalmiaa 6년 전 0

일단 flow 자체가 bfs가 아니라 dfs 같습니다.

구현은 자기 스타일대로 하시는거고, 구현방안을 말씀드리면

bfs로 자기가 갈 수 있는 방향 (동서남북) 을 탐색하면서,

그곳이 "1"인지와, 이미탐색했는지, 그리고 이미 탐색했다면, 몇번만에 도달했는지를 판단하고, 새로 방문하는 depth가 더 짧다면, 값을 갱신하고 또 돌고,

아니면 안돌게끔 구현을 해야 합니다.

지금처럼 next position을 1방향으로 잡으면 구멍이 생길 수 밖에 없습니다.

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

문제

문제

출처

ICPC

너무 어렵네요 왜 틀린지 조언좀 부탁드립니다.

acmbono 6년 전 0

indioindio 6년 전 0

kalmiaa 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말