[JAVA][정올 1671] 색종이 (중)

사이트명	정올
문제 링크	jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=944&sca=2060
주요 알고리즘	탐색, BFS, DFS
사용 언어	Java 자바
설명이 장황합니다.. 도움되는 것만 파악하세요 :-)

1. 문제

 

2. 입력 / 출력

 

 

 

---

3. 풀이

3-1. 생각 노트

둘레 구하는 공식은 평행 사변형이나 정사각형 처럼 일반적인 도형에나 있지, 복잡한 형태는 없다.

따라서 이 문제는 그래프에서 표현되는 도형 특성상 주위를 둘러싸는 녀석들은 카운팅하면 구할 수 있다는 특징을 캐치해야 한다.

배열에 수를 채워넣고, 주위에 아무것도 없는 것들을 조사하여 그 수를 세는 식으로 하면 된다.

 

 

 3-2. 변수명

변수명	설명
dx dy	사방 탐색을 위한
int[][] paper	겹치는 걸 제외하고 색종이를 채우기 위한 용도
boolean[][] isVisit	방문 체크를 위한 변수
round	둘레 저장용

 

3-3. 코드 보기

/**************************************************************
    Problem: 1671
    Language: Java
    Result: Success
    Time:319 ms
    Memory:17664 kb
****************************************************************/
 
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
     
    static int[][] paper = new int[101][101];
    static boolean[][] isVisit = new boolean[101][101];
     
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
     
    static int round = 0;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int N = sc.nextInt();
         
        //입력부
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
             
            for (int r = x; r < x + 10; r++) {
                for (int c = y; c < y + 10; c++) {
                    paper[r][c] = 1;
                }
            }
        }
         
        //둘레 확인
        /* 1. 탐색하다가 1 만나면, 사방탐색
         * 2. 0인 공간 둘레 ++
         * 
         */
         
         
         
        for (int i = 0; i < paper.length; i++) {
            for (int j = 0; j < paper.length; j++) {
                if(paper[i][j] == 1 && !isVisit[i][j]) {
                    bfs(i,j);
                }
            }
        }
 
//      for (int i = 0; i < paper.length; i++) {
//          for (int j = 0; j < paper.length; j++) {
//              System.out.print(paper[i][j]);
//          }
//          System.out.println();
//      }
         
        System.out.println(round);
    }
 
    private static void bfs(int i, int j) {
        Queue<int[]> q = new LinkedList<>();
         
        q.add(new int[] {i,j});
        isVisit[i][j] = true;
         
        while(!q.isEmpty()) {
            int x = q.peek()[0];
            int y = q.poll()[1];
             
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                 
                // 범위 밖 -> 아웃
                if(!(0<= nx && nx < 101 && 0 <= ny && ny < 101)) continue;
                 
                // 인접값이 0이면 체크, 꺾인 부분은 중복 체크 되도록 방문처리 안함
                if(paper[nx][ny] == 0) round++;
                 
                // 다음 값이 탐색 대상(1) 이고, 미방문이면 Q에 넣고 방문처리
                if(paper[nx][ny] == 1 && !isVisit[nx][ny]) {
                    isVisit[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                }
            }
        }
    }
 
}

 

3-4. 마무리

BFS, DFS 진짜 많이 풀었는데.. 몇달 알고리즘 쉬니까 머리 텅텅이다.. 흑흑

 

 

 

 

 

#알고리즘풀이 #정올