글 읽기 - 문제를 계속 틀릴경우 확인해 주세요

tkddufdl77 2년 전 0

정답 코드를 원치 않으시는 분은 뒤로 가기를 눌러주세요. 아래 정답 처리된 코드처럼 방문을 확인할 때 x 와 y값이 서로 바뀌어서 정답 체크가 되는 것 같습니다.(53번 줄, 79번 줄) 문제가 잘 해결되지 않으면 참고해서 제출해보세요!

//BOJ 1584 게임
#include <iostream>
#include <deque>
using namespace std;

struct point {
	int y;
	int x;
	int cost;
};

int main() {
	int dx[4] = { -1, 0, 1, 0 };
	int dy[4] = { 0, -1, 0, 1 };
	int N, M, ans = -1;
	int field[501][501] = { 0 };
	bool visit[501][501] = { false };

	cin >> N;
	while (N--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2) {
			int temp = x1;
			x1 = x2;
			x2 = temp;
		}
		if (y1 > y2) {
			int temp = y1;
			y1 = y2;
			y2 = temp;
		}
		for (int i = x1; i <= x2; i++)
			for (int j = y1; j <= y2; j++)
				field[i][j] = 1;
	}	
	cin >> M;
	while (M--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2) {
			int temp = x1;
			x1 = x2;
			x2 = temp;
		}
		if (y1 > y2) {
			int temp = y1;
			y1 = y2;
			y2 = temp;
		}
		for (int i = x1; i <= x2; i++)
			for (int j = y1; j <= y2; j++)
				visit[i][j] = true;
	}

	deque<point> dq;
	dq.push_back({ 0,0,0 });
	visit[0][0] = true;

	while (!dq.empty()) {
		int curX = dq.front().x;
		int curY = dq.front().y;
		int curCost = dq.front().cost;
		dq.pop_front();

		if (curX == 500 && curY == 500) {
			ans = curCost;
			break;
		}
		for (int i = 0; i < 4; i++) {
			if (curX + dx[i] >= 0 && curX + dx[i] <= 500
				&& curY + dy[i] >= 0 && curY + dy[i] <= 500
				&& !visit[curY + dy[i]][curX + dx[i]])
			{
				if (field[curY + dy[i]][curX + dx[i]] == 0)
					dq.push_front({ curY + dy[i], curX + dx[i], curCost });
				else 
					dq.push_back({ curY + dy[i], curX + dx[i], curCost + 1 });
				visit[curY + dy[i]][curX + dx[i]] = true;
			}
		}
	}
	cout << ans;
	return 0;
}

tkddufdl77 2년 전 0

3달전에 푼 문제라 간략히 보고 답변 드리는점 양해 부탁드립니다. 이 코드에서는 라이프가 적어진 상태로 방문하는경우는 존재하지 않다고 생각됩니다. 라이프 소모가 같을 경우에도 특정 지점부터 종점까지만 확인하면 됨으로 갱신의 필요성을 느끼지 못했습니다. 반례의 경우를 알려주시면 감사하겠습니다.

minjea917 2년 전 0

이제보니 제가 잘못썻네요

지금 올리신 코드가 잘못된게 아닌데. 제가 원글의 x,y 값이 서로 바뀌어서 정답 체크가 된다는 부분을 봤을 때

저는 저 부분을 전혀 고려 안 하고 풀어서 맞았고, 관련 문제에서 방문여부 참거짓으로 풀었다 틀린 적이 있어서 잘못된 코드라고 생각했습니다.

혼란을 드려서 죄송합니다.

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

문제

문제

출처

ICPC

문제를 계속 틀릴경우 확인해 주세요

tkddufdl77 2년 전 0

tkddufdl77 2년 전 0

minjea917 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말