알고리즘 스터디 8월 2주차 문제2 (색종이 -2)

문제#

  • 링크로 대체

풀이 및 주저리..

전에 풀었던 문제보다는 좀 쉬운 난이도의 BFS 문제였다. 처음에는 시뮬레이션 적인 요소가 많다고 생각해서 문제를 도전했다가 결국 둘레는 구하는 식에서 BFS 를 사용하게 되었다. 둘레를 구하는 문제는 가끔 나오기도 하고 활용되는 경우가 많아서 계속해서 코드를 짜면서 익숙해지는게 도움이 많이 될것 같았다. 다른 방법으로 둘레를 구하는 방법이 있다면 그것도 후에 한번 적으러 와야겠다.

코드

package baekjoon.algorithm.simulation;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_2567_ColorPaper {
	static final int MAP_SIZE = 102, PAPER_SIZE = 10;
	static final int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };
	static int[][] map = new int[MAP_SIZE][MAP_SIZE];
	static boolean[][] isVisited = new boolean[MAP_SIZE][MAP_SIZE];
	static int answer = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		for (int i = 0; i < num; i++) {
			int left = sc.nextInt();
			int bottom = sc.nextInt();
			makePaper(left, bottom);
		}
		for (int r = 0; r < MAP_SIZE; r++) {
			for (int c = 0; c < MAP_SIZE; c++) {
				if (!isVisited[r][c] && map[r][c] == 1) {
					countRound(r, c);
				}
			}
		}
		System.out.println(answer);
	}

	private static void countRound(int r, int c) {
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(r);
		que.offer(c);
		isVisited[r][c] = true;
		while (!que.isEmpty()) {
			int x = que.poll();
			int y = que.poll();
			for (int i = 0; i < 4; i++) {
				int mX = x + dx[i];
				int mY = y + dy[i];
				if (map[mX][mY] == 0) {
					answer++;
				} else if (map[mX][mY] == 0 && !isVisited[mX][mY]) {
					isVisited[mX][mY] = true;
					que.offer(mX);
					que.offer(mY);
				}
			}
		}
	}

	private static void makePaper(int left, int bottom) {
		for (int r = bottom; r < bottom + PAPER_SIZE; r++) {
			for (int c = left; c < left + PAPER_SIZE; c++) {
				map[r][c] = 1;
			}
		}
	}

}

기억에 남길 것!

© 2020 JunhoBaik, Built with Gatsby