문제풀이7_DFS, BFS) 연구소

Intro

S기업 코딩테스트 대비 문제풀이를 계속한다.

백준사이트의 문제링크를 첨부한다.

https://www.acmicpc.net/problem/14502

이번 문제는 그동안 연습했던, dfs bfs 모두 사용해야 하는 문제이다.

개인적으로는 그렇게 생각하고 그렇게 풀었다.

오랜만에 디버깅 과정 없이 한번에 정답을 맞춘 문제라 기분이 좋다.

문제를 간단히 설명하자면,

2차원 graph가 주어진다.

0은 빈 공간, 1은 벽, 2는 바이러스의 위치이다.

주어진 graph에서 0 값을 가진 빈 공간에 추가적으로 벽을 3개 세운다.

바이러스는 벽에 가로막히기 전까지 뻗어나갈 수 있다.

결과적으로는 벽을 3개 세우고 바이러스가 뻗어나갔을 때, 바이러스에 전염되지 않는 공간의 최대 값을 찾는 문제이다.

Solution

내 구현과정은 다음과 같다.

0. graph 값을 입력받으면서 바이러스의 위치를 기억해둔다.

1. graph를 완전탐색해서 0인 값에 벽을 세우는 dfs 함수를 구현한다.

2. dfs 안에 다시 벽을 세우는 dfs를 호출하여 재귀함수로 구현한다.

3. 벽이 3개 세워졌으면, bfs 방식을 통해 바이러스가 뻗어 나가는 것을 구현한다. 바이러스에 전염되면 2로 값을 변경시킨다.

4. 이후에 전염되지 않은 0의 갯수를 센다.

Code

	/************
	연구소
	N*M graph
	빈칸 0, 벽 1, 바이러스 2,
	************/
	#include<iostream>
	#include<stdio.h>
	#include<algorithm>
	#include<vector>
	#include<queue>
	using namespace std;
	typedef struct pos {
	int y;
	int x;
	}pos;
	//global var
	int N, M;
	int graph[9][9];
	vector<pos> virus;
	int dx[] = { -1,+1,0,0 };
	int dy[] = { 0,0,-1,+1 };
	int answer = -1;
	//func
	void dfs(pos cur_pos, int count);
	void print();
	void graph_backup(int from[9][9], int to[9][9]);
	void virus_check();
	int main()
	{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	scanf("%d", &graph[i][j]);
	if (graph[i][j] == 2) {
	virus.push_back({ i,j }); //바이러스 위치
	}
	}
	}
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (graph[i][j] == 0) {
	pos cur_pos = { i,j };
	graph[i][j] = 1;
	dfs(cur_pos, 1);
	graph[i][j] = 0;
	}
	}
	}
	printf("%d\n", answer);
	}
	void dfs(pos cur_pos, int count) {
	//print();
	//system("pause");
	if (count == 3) {
	int backup[9][9];
	graph_backup(graph, backup);
	virus_check();
	graph_backup(backup, graph);
	return;
	}
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (graph[i][j] == 0) {
	pos next_pos = { i,j };
	graph[i][j] = 1;
	dfs(next_pos, count + 1);
	graph[i][j] = 0;
	}
	}
	}
	}
	void print() {
	printf("\n");
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	printf("%d ", graph[i][j]);
	}
	printf("\n");
	}
	}
	void virus_check() {
	bool is_visited[9][9] = { false, };
	for (int i = 0; i < virus.size(); i++) {
	queue<pos> q;
	q.push({ virus[i].y, virus[i].x });
	while (!q.empty()) {
	pos cur_virus_node = q.front();
	q.pop();
	for (int d = 0; d < 4; d++) {
	pos next = { cur_virus_node.y + dy[d], cur_virus_node.x + dx[d] };
	if (is_visited[next.y][next.x] == true) continue;
	if (graph[next.y][next.x] == 1)continue;
	if (next.y < 0 || next.y >= N || next.x < 0 || next.x >= M)continue;
	is_visited[next.y][next.x] = true;
	graph[next.y][next.x] = 2;
	q.push(next);
	}
	}
	}
	//print();
	int candi = 0;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (graph[i][j] == 0) {
	candi++;
	}
	}
	}
	if (answer < candi) {
	answer = candi;
	}
	}
	void graph_backup(int from[9][9], int to[9][9]) {
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	to[i][j] = from[i][j];
	}
	}
	}

view raw ss14502.cpp hosted with ❤ by GitHub

Conclusion

바이러스가 뻗어나가는 것을 구현하기 전과 후로 graph를 백업해두고 다시 복원하는 것이 중요했다.

비주얼 스튜디오에서 몇가지 케이스를 테스트 해봤을 때는 너무시간이 오래걸려서 틀리지 않을까 생각했는데,,

막상 돌려보니 맞았다고해서, 오류가 없는 것도 이상하고, 조금 찝찝하다.

추가)

인터넷의 답안 코드들을 찾아보니,

나는 graph 하나로 백업해두고 복원하는 방식을 이용했는데 그럴필요가 없었다.

graph를 그냥 복사하고 그곳에 바이러스가 뻗어나가는 것을 구현해는 방식을 사용해야했다. 운이좋아서 맞은 문제같다. 분발하자.