글 읽기 - 어떤 부분을 생각하지 못했을까요?

recoder1212 4년 전 0

네 방향에 대해서 이미 벽을 부쉈고 0을 지나가는 경우, 아직 벽을 부수지 않았고 0을 지나가는 경우, 아직 벽을 부수지 않았고 벽을 이제 부수는 경우, 그 외(이미 벽을 부쉈고 1은 지나갈 수 없으니 skip)로 분기하였습니다.

질문게시판의 많은 예를 돌려보았고, 나름 만들어서 해 보았는데, -1이 나와야하는 경우이거나 다른 벽을 부수어서 도달하지 못하는 경우 등은 잘 되었습니다. 어떤 부분을 생각하지 못했을까요?

#include <iostream>
#include <queue>
using namespace std;

int map[1005][1005];
bool visited[1005][1005]; // 벽 안부순 방문
bool visited2[1005][1005]; // 벽 부순 방문


struct muzi {
	int n;
	int m;
	bool crashed;
	int count;
};

queue<muzi> q;

int main() {
	int result = 2147483000;
	int N = 1, M = 1;
	cin.tie(0);
	ios_base::sync_with_stdio(false);;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		//string temp;
		//cin >> temp;
		for (int j = 0; j < M; j++) {
			char temp;
			cin >> temp;
			map[i][j] = temp - 48;
			visited[i][j] = false;
			visited2[i][j] = false;
		}
	}
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}*/


	struct muzi start = { 0,0,false,1 };
	q.push(start);
	//int count = 2;
	while (!q.empty()) {
		struct muzi temp = q.front();
		bool tempCrashed = temp.crashed;
		//count++;
		if (temp.n == N - 1 && temp.m == M - 1) {
			cout << temp.count;
			//result = temp.count;
			return 0; // 끝지점 도달할 시 탈출
		}
		q.pop();
		if (temp.n < N - 1 && map[temp.n + 1][temp.m] == 0 && !visited[temp.n + 1][temp.m] && !tempCrashed) { // 아래로 벽 안부숨, 아직 안 부쉈음
			visited[temp.n + 1][temp.m] = true;
			struct muzi temp2 = { temp.n + 1, temp.m, tempCrashed, temp.count+1 };
			q.push(temp2);
		}
		else if (temp.n < N - 1 && map[temp.n + 1][temp.m] == 0 && !visited2[temp.n + 1][temp.m] && tempCrashed) { // 아래로 벽 안부숨, 이미 부쉈음
			visited2[temp.n + 1][temp.m] = true;
			struct muzi temp2 = { temp.n + 1, temp.m, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.n < N - 1 && map[temp.n + 1][temp.m] == 1 && !tempCrashed && !visited2[temp.n + 1][temp.m]) { // 아래로 벽 부숨, 아직 안 부쉈음
			visited2[temp.n + 1][temp.m] = true;
			struct muzi temp2 = { temp.n + 1, temp.m, true, temp.count + 1 };
			q.push(temp2);
		}
		if (temp.m < M - 1 && map[temp.n][temp.m + 1] == 0 && !visited[temp.n][temp.m + 1] && !tempCrashed) { // 오른쪽으로 벽 안부숨
			visited[temp.n][temp.m + 1] = true;
			struct muzi temp2 = { temp.n, temp.m + 1, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.m < M - 1 && map[temp.n][temp.m + 1] == 0 && !visited2[temp.n][temp.m + 1] && tempCrashed) { // 오른쪽으로 벽 안부숨, 이미 부쉈음
			visited2[temp.n][temp.m + 1] = true;
			struct muzi temp2 = { temp.n, temp.m + 1, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.m < M - 1 && map[temp.n][temp.m + 1] == 1 && !tempCrashed && !visited2[temp.n][temp.m + 1]) { // 오른쪽으로 벽 부숨
			visited2[temp.n][temp.m + 1] = true;
			struct muzi temp2 = { temp.n, temp.m + 1, true, temp.count + 1 };
			q.push(temp2);
		}
		if (temp.n > 0 && map[temp.n - 1][temp.m] == 0 && !visited[temp.n - 1][temp.m] && !tempCrashed) { // 위로 벽 안부숨
			visited[temp.n - 1][temp.m] = true;
			struct muzi temp2 = { temp.n - 1, temp.m, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.n > 0 && map[temp.n - 1][temp.m] == 0 && !visited2[temp.n - 1][temp.m] && tempCrashed) { // 위로 벽 안부숨, 이미 부쉈음
			visited2[temp.n - 1][temp.m] = true;
			struct muzi temp2 = { temp.n - 1, temp.m, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.n > 0 && map[temp.n - 1][temp.m] == 1 && !tempCrashed && !visited2[temp.n - 1][temp.m]) { // 위로 벽 부숨
			visited2[temp.n - 1][temp.m] = true;
			struct muzi temp2 = { temp.n - 1, temp.m, true, temp.count + 1 };
			q.push(temp2);
		}
		if (temp.m > 0 && map[temp.n][temp.m - 1] == 0 && !visited[temp.n][temp.m - 1] && !tempCrashed) { // 왼쪽으로 벽 안부숨
			visited[temp.n + 1][temp.m] = true;
			struct muzi temp2 = { temp.n, temp.m - 1, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.m > 0 && map[temp.n][temp.m - 1] == 0 && !visited2[temp.n][temp.m - 1] && tempCrashed) { // 왼쪽으로 벽 안부숨, 이미 부쉈음
			visited2[temp.n + 1][temp.m] = true;
			struct muzi temp2 = { temp.n, temp.m - 1, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.m > 0 && map[temp.n][temp.m - 1] == 1 && !tempCrashed && !visited2[temp.n][temp.m - 1]) { // 왼쪽으로 벽 부숨
			visited2[temp.n][temp.m - 1] = true;
			struct muzi temp2 = { temp.n, temp.m - 1, true, temp.count + 1 };
			q.push(temp2);
		}
	}

	//if (!visited[N-1][M-1] && !visited2[N-1][M-1])
		//result = -1;
	cout << "-1";

	return 0;
}

recoder1212 4년 전 0

왼쪽으로 부수지 않는 경우에 visited 배열의 인덱스를 잘못 적었네요 ㅜㅜ 어떻게 TC들을 맞았던건지..

if (temp.m > 0 && map[temp.n][temp.m - 1] == 0 && !visited[temp.n][temp.m - 1] && !tempCrashed) { // 왼쪽으로 벽 안부숨
			visited[temp.n + 1][temp.m] = true;
			struct muzi temp2 = { temp.n, temp.m - 1, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}
		else if (temp.m > 0 && map[temp.n][temp.m - 1] == 0 && !visited2[temp.n][temp.m - 1] && tempCrashed) { // 왼쪽으로 벽 안부숨, 이미 부쉈음
			visited2[temp.n + 1][temp.m] = true;
			struct muzi temp2 = { temp.n, temp.m - 1, tempCrashed, temp.count + 1 };
			q.push(temp2);
		}

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

문제

문제

출처

ICPC

어떤 부분을 생각하지 못했을까요?

recoder1212 4년 전 0

recoder1212 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말