글 읽기 - 14502번 연구소 문제 도와주세요~~

asdsa2134 5년 전 0

14502 연구소 문제입니다

테케는 전부 맞게 나오는데 제출하면 틀렸다고 나오네요 ㅜㅜ

랜덤으로 테스트 케이스 만들어서 넣어봐도 맞게나와요

도와주세요~~~

풀이는 dfs이용해서 풀었습니다

#include <iostream>
#include <map>
#include <cstdlib>
#include <ctime>
using namespace std;

int X[11], Y[11];
int Map[9][9];
int check[11];
int dfs_visited[9][9];
int index = 0, Count;
int N, M, numberone = 0, ans = 0;
map<pair<int,int>, int> m;

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

void dfs(int x, int y, int ok) {

	for (int i = 0; i < 4; i++) {
		int nx = dx[i] + x;
		int ny = dy[i] + y;

		if (ny >= 0 && ny < N && nx >= 0 && nx < M) { //맵을 벗어나지 않는 좌표일때
			if (Map[ny][nx] != 1 && dfs_visited[ny][nx] != ok) { //벽이 아니면서 체크하지 않았으면
				if (Map[ny][nx] == 2) check[m[{nx, ny}]] = 1; //원래 바이러스자리이면 체크해줌
				Count++; //바이러스 갯수++
				dfs_visited[ny][nx] = ok; //dfs체크
				dfs(nx, ny, ok); //dfs
				//dfs_visited[ny][nx] = 0;
			}
		}
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	//srand((unsigned int)time(NULL));
	//N = rand() % 6 + 3;
	//M = rand() % 6 + 3;
	index = 0; ans = 0;
	printf("%d %d\n", N, M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &Map[i][j]);
			//Map[i][j] = rand() % 3;
			//printf("%d ", Map[i][j]);
			if (Map[i][j] == 2) { // 바이러스 좌표 체크
				Y[index] = i;
				X[index] = j;
				m[{ X[index], Y[index] }] = index; //map에 바이러스 좌표 인덱스 저장
				index++;
			}
			else if (Map[i][j] == 1) numberone++; //벽의 갯수 체크
		}
		//printf("\n");
	}
	//printf("index : %d\n", index);

	int f = 0, s = 1, t = 2, ok = 1; //f, s, t 추가될 첫 둘 세번째 벽 ok <- dfs 체크할때 쓰일 숫자
	while (true) {

		if (f != s && s != t && t != f) { //위치가 같지 않을때
			if (Map[f / M][f % M] == 0 && Map[s / M][s % M] == 0 && Map[t / M][t % M] == 0) { //해당위치가 전부 빈공간일때
				Map[f / M][f % M] = 1; 	   //벽으로 추가
				Map[s / M][s % M] = 1;	   //벽으로 추가
				Map[t / M][t % M] = 1;	   //벽으로 추가

				for (int i = 0; i < index; i++) //바이러스 체크 초기화
					check[i] = 0;

				ok++;
				Count = 0;
				for (int i = 0; i < index; i++) { //바이러스 숫자만큼 반복
					if (!check[i]) { //체크되지 않은 바이러스이면
						check[i] = 1; Count++; //체크후 바이러스 갯수++
						dfs_visited[Y[i]][X[i]] = ok; //dfs 체크
						dfs(X[i], Y[i], ok); //dfs
						//dfs_visited[Y[i]][X[i]] = 0;
					}
					//dfs
				}

				if (ans < M * N - numberone - 3 - Count)ans = M * N - numberone - 3 - Count; //안전공간 계산후 저장

				Map[f / M][f % M] = 0;   //원상복구
				Map[s / M][s % M] = 0;	 //원상복구
				Map[t / M][t % M] = 0;	 //원상복구
			}
		}

		t++;

		if (t == M * N) { //세번째가 끝까지 갔을때
			s++;
			t = s + 1;
		}
		if (s == M * N - 1) { //두번째가 끝까지 갔을 때
			f++;
			s = f + 1;
			t = s + 1;

		}
		if (f == M * N - 2) break;//첫번째가 끝까지 갔을 때

	}
	printf("%d\n", ans);
	return 0;
}

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

문제

문제

출처

ICPC

14502번 연구소 문제 도와주세요~~

asdsa2134 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말