[백준] 14716 현수막

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

14716번: 현수막

 

확실히 그래프(BFS, DFS) 관련 문제는 출제 빈도가 높은 것 같다. 보통 우, 하나 상하좌우 방향만 고려하는데 이 문제는 대각선을 포함한 8가지 방향을 고려해야 됬기 때문에 따로 DIR 배열을 만들어서 반복문을 돌려 처리했다.

 

---

문제 및 입출력

 

---

코드

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

public class Main
{
    static int cnt = 0;
    // 상하좌우 + 대각선 4방향에 대한 모든 경우의 수 8가지
    static int[][] dir = new int[][]{{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
    
    public static void traverse(int[][] map, boolean[][] visit, int i, int j, int maxY, int maxX)
    {
        // BFS 실행값(=결과값)
        cnt++;
        Queue<int[]> q = new LinkedList<int[]>();
        q.add(new int[]{i, j});
        visit[i][j] = true;
        
        // BFS 실행
        while(!q.isEmpty())
        {
            int[] temp = q.poll();
            int y = temp[0];
            int x = temp[1];
            
            // 미리 설정한 8방향을 모두 검사
            for(int loop=0; loop<dir.length; loop++)
            {
                y += dir[loop][0];
                x += dir[loop][1];
                
                // 조건에 맞을 때 다음 순회순서로 설정
                if(y<maxY && y>=0 && x<maxX && x>=0 && map[y][x]==1 && !visit[y][x])
                {
                    visit[y][x] = true;
                    q.add(new int[]{y, x});
                }
                
                y -= dir[loop][0];
                x -= dir[loop][1];
            }
        }
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] map = new int[m][n];
        boolean[][] visit = new boolean[m][n];
        
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                map[i][j] = sc.nextInt();
            }
        }
        
        // 값이 1이고 아직 방문하지 않았을 경우 BFS 초기 좌표로 설정하여 BFS 실행
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(map[i][j]==1 && !visit[i][j])
                {
                    traverse(map, visit, i, j, m, n);
                }
            }
        }
        
        System.out.println(cnt);
        sc.close();
    }
}