글 읽기 - 연구소 문제입니다.

persona_k 5년 전 0

연구소 문제는 푸는 도중 머리를 굴려도 도저히 몰라서 질문 드립니다.

(참고로 아래 코드는 다른 사람이 푼 문제를 참고하여 작성하였습니다..)

문제를 푸는 방향은 이렇게 하였습니다.

1.지도를 입력받는다.

2. '0'인 안전 영역의 위치를 벡터에 넣고, 그것을 뽑아 기둥을 지도에 표시한다.

3. 그 지도에 바이러스는 퍼트린다(dfs로)

4. '0'인 부분을 체크하여 안전영역의 크기가 가장 높은 것을 찾는다.

2~4번을 반복한다.

제가 어려워 하는 부분은 44,45,46번 줄의 코드부분입니다.

문제의 크기가 작기 때문에 브루트 포스(완전탐색)접근 방법으로 가는 것은 알겠으나,

각 3개의 기둥을 뽑을 때, for문 형식을 저렇게 생각할 수 있는 방법이 따로 존재하는 것입니까??

요약하자면, 44,45,46번 코드를 작성하는 노하우를 알고 싶습니다..

읽어주셔서 감사합니다.

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

int map[8][8];
int copymap[8][8];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int N, M;

vector<pair<int, int>> v;

//깊이 우선 탐색
void dfs(int x, int y)
{
	for (int k = 0; k < 4; k++)
	{
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
			if (copymap[nx][ny] == 0) {
				copymap[nx][ny] = 2;
				dfs(nx, ny);
			}
		}
	}
}

int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			copymap[i][j] = map[i][j];
			//0인 안전 영역의 위치만 벡터에 넣는다.
			if (map[i][j] == 0)
				v.push_back(make_pair(i, j));
		}
	}
	int ans = 0;
	for (int i = 0; i < v.size()-2; i++) {
		for (int j = i + 1; j < v.size()-1; j++) {
			for (int k = j + 1; k < v.size(); k++) {
				pair<int, int> one = v[i];
				pair<int, int> two = v[j];
				pair<int, int> three = v[k]; //3개의 좌표 선택

				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						copymap[i][j] = map[i][j];
					}
				}

				//3개의 기둥 세우기
				copymap[one.first][one.second] = 1;
				copymap[two.first][two.second] = 1;
				copymap[three.first][three.second] = 1;

				//dfs를 돌려서 바이러스 전파
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if (copymap[i][j] == 2)
							dfs(i, j);
					}
				}
				int cnt = 0; //안전영역 크기 확인
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if (copymap[i][j] == 0)
							cnt++;
					}
				}
				ans = max(ans, cnt);
			}
		}
	}

	cout << ans << endl;

	return 0;
}

djm03178 5년 전 2

쉽게 생각해서 전체에서 3개를 뽑는 모든 경우의 수를 해보는 것입니다.

뽑는 순서는 중요하지 않으므로 중복된 경우를 제외하기 위해 i, j, k의 순서를 정하고 항상 i<j<k가 되도록 해서, j는 i+1부터 시작하게, k는 j+1부터 시작하게 한 거고요.

persona_k 5년 전 0

쉽게 설명해주셔서 감사합니다!

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

문제

문제

출처

ICPC

연구소 문제입니다.

persona_k 5년 전 0

djm03178 5년 전 2

persona_k 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말