[백준] java 알고리즘 스터디 - DFS/BFS 2

14502 연구소

📌문제 링크

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

💡 문제 풀이

모든 경우의 수를 탐색해야 하므로, 빈 칸 중에서 3개를 조합으로 뽑아 벽을 세운 뒤 안전 영역의 크기를 구한다.

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	// 좌표를 저장할 class 선언
	private static class Pos{
		int r, c;
		public Pos(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	static int N, M;
	static int[][] map;
    // 빈 칸을 저장할 리스트
	static List<Pos> list = new ArrayList<Pos>();
    // 바이러스가 있는 칸을 저장할 리스트
	static List<Pos> virus = new ArrayList<Pos>();
    // 빈 칸의 개수
	static int list_size;
    // 벽을 세울 3개의 칸을 저장할 배열
	static Pos[] walls = new Pos[3];
    // 안전 영역의 최대 크기
	static int max;
    // 사방 탐색
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		
        // 연구소 입력
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(stk.nextToken());
				if (map[i][j] == 0) { // 빈 칸일 경우
					list.add(new Pos(i, j));
				} else if (map[i][j] == 2) { // 바이러스일 경우
					virus.add(new Pos(i, j));
				}
			}
		}
		
		list_size = list.size();
        // 조합으로 벽을 세우는 경우의 수 구함
		combination(0, 0);
		
		System.out.println(max);
		
	}

	private static void combination(int cnt, int start) {
		if (cnt == 3) { // 벽 3개를 세웠을 경우
			simulation();
			return;
		}
		
		for (int i = start; i < list_size; i++) {
			walls[cnt] = list.get(i);
			combination(cnt+1, i+1);
		}
	}

	private static void simulation() {
		// 연구소 map deepcopy
		int[][] tmp = new int[N][M];
		for (int i = 0; i < N; i++) {
			tmp[i] = Arrays.copyOf(map[i], M);
		}
		
        // 벽을 3개 세움
		for (Pos wall : walls) {
			tmp[wall.r][wall.c] = 1;
		}
		
        // 바이러스의 위치를 모두 queue에 넣음
		Queue<Pos> queue = new ArrayDeque<Pos>();
		for (Pos v : virus) {
			queue.offer(v);
		}
		
		while(!queue.isEmpty()) {
			Pos cur = queue.poll();
			
            // 바이러스 퍼뜨리기
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				
				if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if (tmp[nr][nc] != 0) continue;
				
				queue.offer(new Pos(nr, nc));
				tmp[nr][nc] = 2;
			}
		}
		
        // 바이러스를 모두 퍼뜨린 뒤 안전 영역의 크기 계산
		int safe = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (tmp[i][j] == 0) safe++;
			}
		}
		
        // 최댓값 갱신
		max = Math.max(max, safe);
	}

}

2206 벽 부수고 이동하기

📌문제 링크

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

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
	// 좌표, 벽을 부순 여부 저장
	private static class Pos {
		int r, c;
		int isBroken;

		Pos(int r, int c, int isBroken) {
			this.r = r;
			this.c = c;
			this.isBroken = isBroken;
		}
	}

	static int N, M;
	static int[][][] map;
    // 사방 탐색
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split(" ");
		N = Integer.parseInt(tmp[0]);
		M = Integer.parseInt(tmp[1]);

		// map 입력
        // 벽을 부수지 않았을 때, 벽을 부쉈을 때 2가지로 나누어 저장
		map = new int[N][M][2];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j][0] = line.charAt(j) - '0';
				map[i][j][1] = line.charAt(j) - '0';
			}
		}
		
        // (0, 0)에서 출발
		Deque<Pos> queue = new ArrayDeque<>();
		queue.offer(new Pos(0, 0, 0)); // r, c, 벽 부순 여부, 길이
		map[0][0][0] = 1; // 지금까지 간 거리를 map에 저장

		int ans = -1;
		while (!queue.isEmpty()) {
			Pos cur = queue.poll();
			
            // (N, M)에 도착하면 종료
			if (cur.r == N - 1 && cur.c == M - 1) {
				ans = map[cur.r][cur.c][cur.isBroken];
				break;
			}

			// 사방 탐색
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];

				if (nr < 0 || nr >= N || nc < 0 || nc >= M)
					continue;
				
                // 이동할 위치가 벽이 아니면 그대로 이동
				if (map[nr][nc][cur.isBroken] == 0) {
					map[nr][nc][cur.isBroken] = map[cur.r][cur.c][cur.isBroken] + 1;
					queue.offer(new Pos(nr, nc, cur.isBroken));
                
                // 이동할 위치가 벽이면서 벽을 부순 적이 없을 경우
				} else if (cur.isBroken == 0 && map[nr][nc][0] == 1) {
					map[nr][nc][1] = map[cur.r][cur.c][0] + 1;
					queue.offer(new Pos(nr, nc, 1));
				}

			}
		}

		System.out.println(ans);
	}

}