인프런 커뮤니티 질문&답변

part6 구름의개수1 문제 풀다 질문 드립니다.

아래는 제가 bfs로 푼 코드인데요. 케이스는 통과하는데 시간초과가 납니다.

bfs() 매개변수로 int[] start 를 받아서 아래에서 사용했는데, 하위 for문에서 int[] sub 로 배열을 만들어 쓴게 문제인가 싶은데, 이런 일차원 배열 더 쓴다고 시간복잡도가 높아지나? 싶은 생각이 들어 시간 초과 왜나는지 궁금합니다.

public static int solution(int[][] sky) {
    boolean[][] visited = new boolean[sky.length][sky[0].length];
    int count = 0;

    for(int i=0; i<sky.length; i++) {
        for(int j=0; j<sky[0].length; j++) {
            if(!visited[i][j] && (sky[i][j] == 1)) {
                bfs(sky, new int[]{i,j}, visited);
                count++;
            }
        }
    }

    return count;
}

public static void bfs(int[][] sky, int[] start, boolean[][] visited) {
    Queue<int[]> q = new ArrayDeque<>();
    q.offer(start);
    visited[start[0]][start[1]] = true;

    while(!q.isEmpty()) {
        int[] cur = q.poll();
        System.out.println("start: " + start[0] + start[1] + "/ poll: " + cur[0] + ", " + cur[1]);

        // cur의 상하좌우 중 갈 수 있는 길 & visited 안한 길을 q에 넣기
        int[] r = {-1, 1, 0, 0};
        int[] c = {0, 0, -1, 1};
        int w = sky[0].length;
        int h = sky.length;

        for(int i=0; i<r.length; i++) {
            int[] sub = new int[]{cur[0]+r[i], cur[1]+c[i]};
            System.out.println("sub:" + sub[0] + ","+sub[1]);
            if((sub[0] >= 0 && sub[0] < h && sub[1] >= 0 && sub[1] < w) && (sky[sub[0]][sub[1]] != 0) && (!visited[sub[0]][sub[1]])) {
                q.offer(sub);
                visited[sub[0]][sub[1]] = true;
                System.out.println("sub offer:" + sub[0] + ","+sub[1]);
            }
        }

    }
}