문제 바로가기

접근방식

처음엔 아 열마다 반복문 돌리면서 bfs돌리면 되겠다 하고 단순하게 생각했다.
답은 맞췄는데 시간초과가 났다.

처음코드(시간초과)

//답은 맞지만 시간초과

import java.io.*;
import java.util.*;

class 석유시추 {
    static boolean[][] visited;
    static int[] dx={0,0,1,-1};
    static int[] dy={1,-1,0,0};
    static int[][] land2;
    static int cnt;
    static int n,m;

    public int solution(int[][] land) {
        int answer = 0;
        n=land.length;
        m=land[0].length;
        land2=land;
        int max=0;

        for(int i=0;i<m;i++){
            visited=new boolean[n][m];
            cnt=0;
            for(int j=0;j<n;j++){
                if(!visited[j][i] && land2[j][i]==1){
                    cnt=bfs(j,i);
                }
            }
            max=Math.max(max, cnt);
        }
        answer=max;
        return answer;
    }

    static int bfs(int x,int y){
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{x,y});
        visited[x][y]=true;
        cnt++;

        while(!q.isEmpty()){
            int[] c=q.poll();
            int cx=c[0];
            int cy=c[1];

            for(int i=0;i<4;i++){
                int nx=cx+dx[i];
                int ny=cy+dy[i];

                if(isEdge(nx,ny) || visited[nx][ny]) continue;

                if(land2[nx][ny]==1){
                    q.offer(new int[]{nx,ny});
                    visited[nx][ny]=true;
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static boolean isEdge(int x,int y){
        return x<0||y<0||x>=n||y>=m;
    }
}

두번째코드

그래서 GPT한테 자문을 구했다...
열마다 석유양을 저장하는 배열을 만들고 bfs는 한번만 돌려서 저장해놓고 배열 중 가장 큰 것을 출력하면 되잖아?

import java.io.*;
import java.util.*;

class 석유시추2 {
    static boolean[][] visited;
    static int[] dx={0,0,1,-1};
    static int[] dy={1,-1,0,0};
    static int[][] land2;
    static int n,m;
    static int[] oil_list; //열마다 석유개수 저장

    public int solution(int[][] land) {
        n=land.length;
        m=land[0].length;
        land2=land;
        oil_list=new int[m];
        int max=0;
        visited=new boolean[n][m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j] && land2[i][j]==1){
                    bfs(i,j);
                }
            }
        }

        for(int i=0;i<m;i++){
            max=Math.max(max,oil_list[i]);
        }

        return max;
    }

    static void bfs(int x,int y){
        int cnt=0;
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{x,y});
        Set<Integer> columns=new HashSet<>();
        columns.add(y);
        visited[x][y]=true;
        cnt++;

        while(!q.isEmpty()){
            int[] c=q.poll();
            int cx=c[0];
            int cy=c[1];

            for(int i=0;i<4;i++){
                int nx=cx+dx[i];
                int ny=cy+dy[i];

                if(isEdge(nx,ny) || visited[nx][ny]) continue;

                if(land2[nx][ny]==1){
                    q.offer(new int[]{nx,ny});
                    visited[nx][ny]=true;
                    columns.add(ny);
                    cnt++;
                }
            }
        }

        for(int i:columns){
            oil_list[i]+=cnt;
        }

    }

    static boolean isEdge(int x,int y){
        return x<0||y<0||x>=n||y>=m;
    }
}

아맞다
bfs함수 안에서 열을 저장하는 리스트를 만들어서 if(columns.contains(ny)) columns.add(ny);이렇게 구현했었는데 시간초과가 났다.
알고보니 contains 함수가 시간을 많이 잡아먹는단다...
그래서 HashSet을 사용하여 자동으로 중복제거되게 해주었다.
근데 처음에 hashSet으로 써서 또 틀렸던건 안비밀