글 읽기 - [틀렸습니다.]어떠한 알고리즘이 잘못된걸까요...

wony6731 4년 전 0

저는 방을 Q와 lightQ 두 가지 큐로 관리를 하고 있습니다.

(1,1)과 연결되어 갈 수 있는 붉이 켜진 방 A를 Q에 삽입하여 방 A에서 킬 수 있는 방들을 켜줍니다.

(1,1)과 연결되어 있지 않으나 추후에 방들이 불이 켜짐으로써 연결될 가능성이 있는 방들은 lightQ에 삽입하여 재탐색해주는 과정을 거치게 됩니다.

chk 변수를 통해 더이상 변화가 없을 경우 while문을 빠져나와 최종적으로 붉이 켜져 있는 방을 출력하게 됩니다.

질문게시판에 올라와 있던

5 25

5 3 4 3

1 1 1 3

1 3 2 2

4 2 4 3

1 1 1 2

1 4 3 5

5 1 3 1

5 3 5 2

4 3 4 5

5 4 3 1

5 4 3 4

3 4 5 4

3 3 4 3

3 3 1 5

1 2 2 1

4 5 3 1

1 4 3 3

4 5 1 3

2 1 5 1

3 5 5 1

2 1 1 4

4 3 5 4

1 3 2 3

3 3 5 2

1 2 3 1

->16

테스트 케이스도 수행해보았으나 잘돌아가는데,,, 혹시 어느 부분이 문제인지 알 수 있을까요 ㅜㅜ

/*
	Title : 불켜기
	Description
		- 최대한 많은 방에 불키기
		- 불이 켜져있는 방으로만 이동 가능
		- 불을 킬 수 있는 최대 개수는
	Solution
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Node{
	int x;
	int y;
};
int N, M, ans;
bool board[2][101][101];	// 불 켜진 상태, [0]은 갈 수 있는 불켜진 곳, [1]은 갈 수 없지만 불켜진 곳
vector<pair<int, int>> V[101][101];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
queue<Node> Q;
queue<Node> lightQ;	// 불은 켜졌지만 갈 수 없는 방

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		V[a][b].push_back(make_pair(c, d));
	}
	board[0][1][1] = true;
	ans = 1;

	// Implementation
	for (int i = 0; i < V[1][1].size(); i++){
		struct Node start;
		start.x = V[1][1][i].second;
		start.y = V[1][1][i].first;

		if (board[0][start.y][start.x]) continue;

		Q.push(start);
		board[1][start.y][start.x] = true;
		ans++;
	}
	bool chk = false;
	while (!Q.empty()){
		auto cur = Q.front();
		Q.pop();

		bool flag = false;
		for (int dr = 0; dr < 4; dr++){
			int nx = cur.x + dx[dr];
			int ny = cur.y + dy[dr];

			if (nx<1 || ny<1 || nx>N || ny>N) continue;
			
			// 갈 수 있는 방이면
			if (board[0][ny][nx]){
				chk = true;
				flag = true;
				break;
			}
		}

		if (flag == true){
			board[0][cur.y][cur.x] = true;
			// 해당 방에 스위치 켜기
			for (int i = 0; i < V[cur.y][cur.x].size(); i++){
				struct Node next;
				next.x = V[cur.y][cur.x][i].second;
				next.y = V[cur.y][cur.x][i].first;

				if (board[0][next.y][next.x]) continue;

				Q.push(next);
				board[1][next.y][next.x] = true;
				ans++;
			}
		}
		else{
			struct Node add;
			add.x = cur.x;
			add.y = cur.y;
			lightQ.push(add);
		}

		if (Q.empty()){
			if (chk == false)
				break;
			chk = false;
			Q = lightQ;
			while (!lightQ.empty())
				lightQ.pop();
		}
	}
	cout << ans << "\n";

	/*for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			cout << board[0][i][j] << " ";
		}
		cout << "\n";
	}*/

	return 0;
}

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

문제

문제

출처

ICPC

[틀렸습니다.]어떠한 알고리즘이 잘못된걸까요...

wony6731 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말