ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 14502.연구소
    알고리즘/백준 BAEK JOON 2020. 5. 25. 07:09

    이번 문제는 연구소이다. 꽤 많이 중요한 내용을 배우고 상기할 수 있는 문제였다.

     

    14502번: 연구소

    인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크�

    www.acmicpc.net

    이 문제를 푸는데 핵심은 맵을 복사해서 사용한다는 것과 나머지는 탐색이다.

    난이도는 어려운 수준이 아닌 거 같지만 초보자에게 연습하기는 좋은 문제인 것 같다( 난 초보자 ㅠㅠ.. 너무좋네...)

    재귀함수 관련된 문제를 조금 더 풀어봐야할 것 같다.


    * 문제풀면서 중요한점

    1. 문자, 특수기호 실수

    => 실수로 자꾸 if문 다음에 변수에 값을 대입할 때 "=" 대신 "=="를 사용하여 틀림 주의

    => 2중 for문 돌릴 때 변수값을 잘봐야한다 => n과 m인데 n과 n으로 처리하는 경우 주의

     

    2. 맞다고 생각한 로직을 조심해라

    => 당연히 맞아야하는데 뭔가 원하는대로 결과가 안나올때는 구현한 로직중에 "여긴 당연히 맞았을거고, 틀린게 없어"라고

         생각한 부분을 다시보거나 다시 생각해라 => 거기가 틀렸을 가능성이 제일 높다!!

     

    3. 배열 값 실수

    => MAX 값을 너무 작게 주지 않은건 아닌지 확인해라.

    => 동적할당은 되도록이면 사용하지말자 => 실수할 수도 있고 초기화를 잘못하면 답이 꼬여버림

     

    4. freopen은 제출할 때 주석처리 해줘야한다.

     

    5. ++ 보다는 +=를 쓰자.

    => 이거 잘못 생각하고 처리하면 답없다..


     

    < Code 설명 >

    //#pragma warning(disable:4996)
    #include <iostream>
    #include <queue>
    #include <algorithm>
    
    #define MAX 9
    using namespace std;
    
    
    int n, m;
    int map[MAX][MAX];    // map이 저장되는 공간
    int c_map[MAX][MAX];  // map을 복사해서 사용할 공간(map이 변하니까)
    
    int dx[4] = { 0, 0, 1, -1 }; //상하좌우
    int dy[4] = { 1, -1, 0, 0 }; //상하좌우
    
    int answer = 0; // 안전한구역의 최대값이 저장될 변수
    queue<pair<int, int>> tmp; // virus 좌표가 저장될 큐
     
    void copy_map(int (*a)[MAX], int(*b)[MAX]){ // 2차원 배열 복사
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < m; j++){
    			a[i][j] = b[i][j];
    		}
    	}
    }
    void virus_work(){ // 바이러스가 퍼짐 (BFS)
    	int virus_map[MAX][MAX];   //바이러스가 퍼질 맵 준비
    	copy_map(virus_map, c_map);//벽세운 맵을 바이러스가 퍼질맵에 복사
    
    	queue<pair<int, int>> virus;// 바이러스 좌표가 저장될 큐
    	virus = tmp; // 처음에 저장한 좌표를 옮김(바이러스 퍼지면 큐가 사라지기때문에)
    
    	while (!virus.empty()){ 
    		int x = virus.front().first; // x좌표
    		int y = virus.front().second;// y좌표 옮기고
    		virus.pop();  // pop 해줌
    		for (int i = 0; i < 4; i++){ //상하좌우 탐색
    			int ax = x + dx[i];
    			int ay = y + dy[i];
    
    			if (ax < 0 || ay < 0 || ax > n || ay > m) //맵 내에 존재해야함
    				continue; // 그게아니면 넘어가
    			if (virus_map[ax][ay] == 0){ // 안전한 공간이 있으면
    				virus_map[ax][ay] = 2;   // 바이러스로 뒤덮음
    				virus.push(make_pair(ax, ay)); // 그리고 덮은 좌표들 큐에저장
    			}
    		}
    	}
    	int cnt = 0; // 안전한 공간이 cnt될 변수
    	for (int i = 0; i < n; i++){     
    		for (int j = 0; j < m; j++){
    			if (virus_map[i][j] == 0) // 안전한 공간이 있다면
    				cnt += 1; // count 한다.
    		}
    	}
    	answer = max(answer, cnt); // 최대값 구함
    }
    void wall(int cnt){ // 백을 세우는 로직 (재귀함수)
    	if (cnt == 3){  // 탈출 구문 => 벽이 3개면
    		virus_work(); // 바이러스 작동
    		return; // 탈출
    	}
    
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < m; j++){
    			if (c_map[i][j] == 0){ // 안전한 공간이면
    				c_map[i][j] = 1;   // 벽을 세움
    				wall(cnt + 1);     // 다음벽을 세우기 위한 재귀
    				c_map[i][j] = 0;   // 그 다음 조합을 위해 0으로 초기화
    			}
    		}
    	}
    }
    int main() {
    	//freopen("14502.txt", "r", stdin); // 디버깅용
    	cin >> n >> m;
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < m; j++){
    			cin >> map[i][j];
    			if (map[i][j] == 2) // 바이러스 좌표 미리 저장
    				tmp.push(make_pair(i, j));
    		}
    	}
    
    	copy_map(c_map, map); // 맵을 복사함
    	for (int i = 0; i < n; i++){
    		for (int j = 0; j < m; j++){
    			if (map[i][j] == 0){ // 0일 경우
    				c_map[i][j] = 1; // 벽을 세움
    				wall(1);         // 하나 세웠으니까 1로시작
    				c_map[i][j] = 0; // 다음 조합을 위해 0으로 초기화
    			}
    		}
    	}
    	cout << answer << "\n";
    	return 0;
    }

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1012.유기농 배추  (0) 2020.05.26
    7576.토마토  (0) 2020.05.25
    14502.연구소  (0) 2020.05.25
    2667.단지번호붙이기  (0) 2020.05.21
    15649 ~ 15652.N과 M(1~4)  (0) 2020.05.20
    1541.잃어버린 괄호  (2) 2020.05.18

    댓글 0

Designed by Tistory.