[알고리즘] 프로그래머스 카카오프렌즈 컬러링북 -2017 카카오코드 예선, bfs, dfs-

 

https://programmers.co.kr/learn/courses/30/lessons/1829?language=java

프로그래머스

 

 

처음 문제를 보고 BFS를 사용해서 큐로 풀어야겠다고 생각했고 테스트 통과도 잘 통과되었습니다.

하지만 제출을 하니 계속 실패가 뜨더라고요. 

그래서 다른 케이스도 해봤으나 다 맞길래 질문하기에 들어가보니 이 문제는 테스트 실행이 아닌 

제출하기에서는 전역변수를 전역변수에서 바로 초기화 해놓으면 안되고 solution 함수 내에서 초기화를 해줘야 한다더라고요.  옛날 문제라 그런가.. 왜..

그래서 전역변수를 solution 함수 내에서 초기화 해줬더니 바로 통과했습니다.

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(6, 4, new int[][]{{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}});
    }

    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static int[][] map;
    public static boolean[][] visited;
    public static ArrayList<Integer> biggestSizeResult = new ArrayList<>(); // 모든 영역크기 리스트
    public static int domainCountResult = 0; // 영역의 수

    public int[] solution(int m, int n, int[][] picture) {

를 다음과 같이 변경

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(6, 4, new int[][]{{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}});
    }

    public static int[] dx;
    public static int[] dy;
    public static int[][] map;
    public static boolean[][] visited;
    public static ArrayList<Integer> biggestSizeResult; // 모든 영역크기 리스트
    public static int domainCountResult; // 영역의 수

    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        dx = new int[]{-1, 0, 1, 0};
        dy = new int[]{0, -1, 0, 1};
        biggestSizeResult = new ArrayList<>();
        domainCountResult = 0;
        

 

 

저처럼 시간 날리는분 없길 바랍니다. ㅎㅎ

 

예전에 백준 dfs, bfs 단계별 풀기에서의 단지번호붙이기 문제와 좀 비슷합니다. 조건만 알맞게 바꿔주면 됩니다.

https://youngest-programming.tistory.com/191?category=873090

[알고리즘] 백준 2667 단지번호붙이기 -dfs, bfs-

 

 

 

풀이는 다음과 같습니다. 

[전역변수에서 초기화해주어 제출시 에러났던 코드]

import java.util.*;

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(6, 4, new int[][]{{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}});
    }

    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static int[][] map;
    public static boolean[][] visited;
    public static ArrayList<Integer> biggestSizeResult = new ArrayList<>(); // 모든 영역크기 리스트
    public static int domainCountResult = 0; // 영역의 수

    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];

        map = new int[m + 2][n + 2];
        visited = new boolean[m + 2][n + 2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i + 1][j + 1] = picture[i][j];
            }
        }

        //모든 배열 인덱스 시작점으로 탐색
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (map[i][j] != 0 && visited[i][j] == false) { //영역 결과값 추출
                    bfs(i, j);
                    domainCountResult++;
                }
            }
        }

        //지금까지의 영역수 오름차순 정렬
        Collections.sort(biggestSizeResult, Comparator.reverseOrder());
        //결과 세팅
        answer[0] = domainCountResult;
        answer[1] = biggestSizeResult.get(0);
        System.out.println(answer[0] +" " + answer[1] );
        return answer;
    }

    public static void bfs(int x, int y) {
        int totalSize = 1;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if ((map[x2][y2] == map[x][y]) && visited[x2][y2] == false) { //방문 안하고 이전값과 같으면 추가(동일한 색인 경우)
                    visited[x2][y2] = true;
                    totalSize++;
                    queue.offer(new Point(x2, y2));
                }
            }
        }
        // 최고 영역 크기값 추출 (추후 정렬)
        biggestSizeResult.add(totalSize);
    }

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

 

 

 

[전역변수 solution 내에서 초기화 해주어 통과한 코드]

import java.util.*;

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(6, 4, new int[][]{{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}});
    }

    public static int[] dx;
    public static int[] dy;
    public static int[][] map;
    public static boolean[][] visited;
    public static ArrayList<Integer> biggestSizeResult; // 모든 영역크기 리스트
    public static int domainCountResult; // 영역의 수

    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        dx = new int[]{-1, 0, 1, 0};
        dy = new int[]{0, -1, 0, 1};
        biggestSizeResult = new ArrayList<>();
        domainCountResult = 0;

        map = new int[m + 2][n + 2];
        visited = new boolean[m + 2][n + 2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i + 1][j + 1] = picture[i][j];
            }
        }

        //모든 배열 인덱스 시작점으로 탐색
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (map[i][j] != 0 && visited[i][j] == false) { //영역 결과값 추출
                    bfs(i, j);
                    domainCountResult++;
                }
            }
        }

        //지금까지의 영역수 오름차순 정렬
        Collections.sort(biggestSizeResult, Comparator.reverseOrder());
        //결과 세팅
        answer[0] = domainCountResult;
        answer[1] = biggestSizeResult.get(0);
        System.out.println(answer[0] + " " + answer[1]);
        return answer;
    }

    public static void bfs(int x, int y) {
        int totalSize = 1;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = point.x + dx[i];
                int y2 = point.y + dy[i];
                if ((map[x2][y2] == map[x][y]) && visited[x2][y2] == false) { //방문 안하고 이전값과 같으면 추가(동일한 색인 경우)
                    visited[x2][y2] = true;
                    totalSize++;
                    queue.offer(new Point(x2, y2));
                }
            }
        }
        // 최고 영역 크기값 추출 (추후 정렬)
        biggestSizeResult.add(totalSize);
    }

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

 

댓글과 공감은 큰 힘이됩니다. 감사합니답!