글 읽기 - 차이점을 모르겠어요!! 도와주세요!!

wjavm2 4년 전 0

안녕하세요 벽부수기만 몇일째 보고있습니다.

근데 한끗차이로 틀리고 맞고가 결정되는데 저는 코드의 차이점을 잘 모르겟어요!ㅜㅜ

아시는분 설명좀해주시면 정말 감사하겠습니다..

아래올린 코드는 정답코드인데요

주석을 처리해 놓은 부분이 제가 헷갈리는 부분입니다.

주석을 달아놓은 부분을 맨윗부분 주석Q1,Q2처럼 고치면 왜 틀리다고 하는지...

제가 보기엔 아무리 봐도 같은 코드인거같은데 제가 뭘 잘못생각하고 있는지 알려주시면 정말 감사하겠습니다.. 답답하네요!

//queue에 넣기전에 미리 canbroken을 정해주는것과 
//아래의 맞은 코드의 주석처럼 queue에서 canbroken을 처리하는 것에 무슨차이가 있을까요..?


/*
Q1.

 if (map[nx][ny] == 1 && canbroken == 1)
 {
    canbroken--; //벽을 부수었으므로, 부실수있는 벽의 갯수를 줄인다.
    Q.push(make_pair(make_pair(nx, ny), canbroken));
	visit[nx][ny][canbroken] = visit[curx][cury][canbroken+1] + 1;
 }
*/

/*
Q2.

 if (map[nx][ny] == 1 && canbroken == 1)
 {
    canbroken = 0; //벽을 부수었으므로, 벽을 부수었다는 표시를 해준다.
    Q.push(make_pair(make_pair(nx, ny), canbroken));
	visit[nx][ny][canbroken] = visit[curx][cury][canbroken+1] + 1;
 }
*/

#include<cstdio>
#include<cstdlib>
#include<queue>

using namespace std;

queue<pair<pair<int, int>, int>> Q;

int map[1000][1000];
int visit[1000][1000][2] = { 0 };
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };

int BFS(int N, int M) {

	visit[0][0][1] = 1;
	Q.push(make_pair(make_pair(0, 0), 1));

	while (!Q.empty())
	{
		int curx = Q.front().first.first;
		int cury = Q.front().first.second;
		int canbroken = Q.front().second;
		Q.pop();

		if (curx == N - 1 && cury == M - 1)
			return visit[N - 1][M - 1][canbroken];

		for (int i = 0; i < 4; i++)
		{
			int nx = curx + dx[i];
			int ny = cury + dy[i];

			if (nx < 0 || ny < 0 || nx > N-1|| ny > M-1) continue;
			if (map[nx][ny] == 0 && visit[nx][ny][canbroken] == 0)
			{
				Q.push(make_pair(make_pair(nx, ny), canbroken));
				visit[nx][ny][canbroken] = visit[curx][cury][canbroken] + 1;
			}
			/*
            if (map[nx][ny] == 1 && canbroken == 1){
				Q.push(make_pair(make_pair(nx, ny), canbroken-1));
				visit[nx][ny][canbroken-1] = visit[curx][cury][canbroken] + 1;
			}
            */
		}
	}

	return -1;
}

int main() {

	int N, M, i, j;

	scanf("%d %d", &N, &M);
	
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			scanf("%1d", &map[i][j]);
		}
	}

	int result = BFS(N, M);

	printf("%d", result);

	return 0;
}

typhoon 4년 전 0

canbroken 변수의 값을 변경해서 아닌가요? 다음 좌표를 탐색하기 위한 포문 내에서 변경한 값으로 동작하기때문에

Q1 처럼 쓰실려면 12줄 밑에 canbroken++; 해주시면 될 것 같네요

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

문제

문제

출처

ICPC

차이점을 모르겠어요!! 도와주세요!!

wjavm2 4년 전 0

typhoon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말