SW 역량테스트 - [백준] 연구소 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/14502

해답 코드 : 

 

// c++

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

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

int inputMap[8][8];
int tempMap[8][8];
int n, m;
int ans = 0;



//지도 복사
void copyMap(int a[8][8], int b[8][8]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j] = b[i][j];
		}
	}
}

//바이러스 퍼트리기(BFS)
void BFSforVirus() {
	//AfterSpreadMap은 3개의 벽을 세운 후 바이러스가 퍼졌을 때의 연구소의 상황을 저장하는곳.
	int AfterSpreadMap[8][8];
	copyMap(AfterSpreadMap, tempMap);
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (AfterSpreadMap[i][j] == 2)
				q.push(make_pair(i, j));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			// 감염되지 않은 영역만 선택
			if (0 <= newX && newX<n && 0 <= newY && newY<m) {
				if (AfterSpreadMap[newX][newY] == 0) {
					AfterSpreadMap[newX][newY] = 2;
					q.push(make_pair(newX, newY));
				}
			}
		}
	}
	//연구소에 오염되지 않은 부분 체크.
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (AfterSpreadMap[i][j] == 0)
				cnt++;
		}
	}
	ans = max(ans, cnt);
}

// 벽을 세우는 재귀 함수 
void recursiveWall(int cnt) {
	// 종료 부, 바이러스를 퍼트려서 오염되지 않은 부분의 갯수를 확인한다.
	if (cnt == 3) {
		BFSforVirus();
		return;
	}
	//벽 세우는 부분.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (tempMap[i][j] == 0) {
				tempMap[i][j] = 1; // 해결 부, 실제로 벽을 세우는 부분
				recursiveWall(cnt + 1); // 분할 부, cnt를 ++ 시켜 벽을 세워야하는 갯수를 -1 시키면서 문제를 분할.				
				tempMap[i][j] = 0;
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &inputMap[i][j]);
		}
	}
	//연구소에서 0인 부분을 모두 벽을 세워야 하므로 다음과 같이 진행.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (inputMap[i][j] == 0) {
				copyMap(tempMap, inputMap);
				tempMap[i][j] = 1;
				recursiveWall(1);
				tempMap[i][j] = 0;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

 

 

// java

import java.util.ArrayList;
import java.util.Scanner;

class pos {

    int x;
    int y;

    pos(int i, int j) {
        x = i;
        y = j;
    }
}


class Main {

    static int area = 0;
    static int N, M, V;

    static void build_wall(int[][] map, int x, int y, int cnt, ArrayList<pos> virus) {

        // restore original map after spreading virus
        if (cnt == 3) {

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

            spread_v(map, virus);
            area = Math.max(area, count_zero(map));

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

        int j = y;

        for (int i = x; i < N; i++, j = 0) {
            for (; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    build_wall(map, i, j+1, cnt+1, virus);
                    map[i][j] = 0;
                }
            }
        }

    }


    static void spread_v(int[][] map, ArrayList<pos> virus) {

        // when spread is over, call count_zero
        // BFS, add to myQ
        ArrayList<pos> myQ = new ArrayList<>();

        for (int i = 0; i < virus.size(); i++) {
            pos temp = virus.get(i);
            int x = temp.x;
            int y = temp.y;

            if (x+1 < N && map[x+1][y] == 0) {
                map[x+1][y] = 2;
                myQ.add(new pos(x+1, y));
            }

            if (y+1 < M && map[x][y+1] == 0) {
                map[x][y+1] = 2;
                myQ.add(new pos(x, y+1));
            }

            if (x-1 >= 0 && map[x-1][y] == 0) {
                map[x-1][y] = 2;
                myQ.add(new pos(x-1, y));
            }

            if (y-1 >= 0 && map[x][y-1] == 0) {
                map[x][y-1] = 2;
                myQ.add(new pos(x, y-1));
            }

        }

        while (!myQ.isEmpty()) {
            spread_v(map, myQ);
            myQ.remove(0);
        }


        /*
        // Nowhere else to spread the virus
        if (virus.isEmpty()) {
            area = Math.max(area, count_zero(map));
        } else {
            spread_v(map, virus);
        }
         */

    }


    static int count_zero(int[][] map) {

        int zero = 0;

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

        return zero;

    }


    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        int[][] map = new int[N][M];
        ArrayList<pos> virus = new ArrayList<>();

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 2) {
                    virus.add(new pos(i, j));
                }
            }
        }


        build_wall(map, 0, 0, 0, virus);


        System.out.println(area);


        sc.close();


    }
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제