• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

3주차 개념 강의에서 첫 문제(연구소_14502) 질문드립니다!!

23.01.22 22:23 작성 조회수 255

0

안녕하세요 선생님ㅠㅠ

제가 푼 코드를 실행시키니 틀렸다고 결과가 나왔는데 아무리 계속 원인을 찾아보고 디버깅도 해봐도 이유를 잘 모르겠습니다ㅠㅠㅜ 반례 중에 어떤 특정한 케이스에서 틀렸다고 판단된 것 같은데 혹시 무엇이 잘못되었는지 짚어주실 수 있으실까요..??

항상 감사합니다 :)

http://boj.kr/34786960e9b84876be27b66b0271ece2

답변 1

답변을 작성해보세요.

1

안녕하세요 ㅎㅎ 주석 달았는데 참고 부탁드립니다.

그리고 담부턴 질문 주실 때 해당 강의 2 - k 등 그런 강의 옆에 질문하기로 좀 부탁드립니다. ㅎㅎ

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int mapp[8][8], sero, garo, MAX_candidate;
// {0, } 이거 하지 말아주세요. 교안참고해주세요.
int MAX = -1, virus_scale = 0, visited[8][8] = {0,}, dy[4] = { 1, 0, -1, 0 }, dx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> v;

void DFS(int ny, int nx);

int main(void)
{
	cin >> sero >> garo;

	for (int i = 0; i < sero; i++)
	{
		for (int k = 0; k < garo; k++)
		{
			cin >> mapp[i][k];

			if (!mapp[i][k])
			{
				v.push_back({ i, k }); // 현재 값이 0인 지점은 전부 vector에 넣는다.
				// 자동으로 초기의 안전영역 크기(v.size())를 알 수 있고, 바이러스 퍼진 후 안전영역은
			}// 초기 v.size() - 커넥티드 컴포넌트 전체 크기(2개수) - 3이다.
		}
	}
    //이걸 왜하시죠? 벽을 3개를 세운담에 해야되는데요. 
	for (int u = 0; u < sero; u++)
	{
		for (int j = 0; j < garo; j++)
		{ 
			if (!visited[u][j] && mapp[u][j] == 2)
			{
				DFS(u, j);
			}
		}
	}

    // 왜 long unsigned intf를 쓰죠?
	for (long unsigned int e = 0; e < v.size(); e++)
	{
		for (long unsigned int w = e + 1; w < v.size(); w++)
		{
			for (long unsigned int q = w + 1; q < v.size(); q++)
			{
				// 여기서 각각 v[e], v[w], v[q] 쌍은 pair쌍 좌표임.
				mapp[v[e].first][v[e].second] = 1;
				mapp[v[w].first][v[w].second] = 1;
				mapp[v[q].first][v[q].second] = 1;

				for (int u = 0; u < sero; u++)
				{
					for (int j = 0; j < garo; j++)
					{
						if (!visited[u][j] && mapp[u][j] == 2)
						{
							DFS(u, j);
						}
					}
				}
				MAX_candidate = v.size() - virus_scale - 3;
				if (MAX < MAX_candidate)
				{
					MAX = MAX_candidate;
				}
				fill(&visited[0][0], &visited[0][0] + 8 * 8, 0); // 이 줄 부터 오류임
				mapp[v[e].first][v[e].second] = 0;
				mapp[v[w].first][v[w].second] = 0;
				mapp[v[q].first][v[q].second] = 0;
				virus_scale = 0;
			}
		}
	}
	cout << MAX << '\n';
	return 0;
}

void DFS(int ny, int nx)
{
	visited[ny][nx] = 1;
	int tmp_y, tmp_x;

	for (int t = 0; t < 4; t++)
	{
		tmp_y = ny + dy[t];
		tmp_x = nx + dx[t];

		if (tmp_y >= 0 && tmp_x >= 0 && tmp_y < sero && tmp_x < garo && !visited[tmp_y][tmp_x])
		{
			if (mapp[tmp_y][tmp_x] != 1)
			{
				if (mapp[tmp_y][tmp_x] != 2)
				{
					virus_scale++;
				}
				DFS(tmp_y, tmp_x);
			}
			 // 아까 &asum할 때 주소로 안하면 이 변경 반영 안되었는데
			// 근데 또 지금까지 했을 때는 ++ 잘 되었던 것 같은데 뭐지
			//
		}
	}
}

아 네넵ㅠㅠ 감사합니다 선생님