프로그래머스 PCCP 2번문제

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/250136

소스코드

package programmers;

import java.util.ArrayList;
import java.util.List;

public class PCCP기출문제_2번 {
    //처음에 문제를 풀이할 때, map을 복사하여 석유량을 Count하였으나, 시간초과 발생
    //다른방법을 찾아보자 map을 순회하면서 석유가 매장되어 있는 부분의 값을 Unique한 값으로 바꿔주자.
    static int width, height;
    static List<Integer> oilAmount;
    static int[][] srcMap, countMap;
    static boolean [] visited;
    static int count;
    static int [] dx = {0,0,1,-1};
    static int [] dy = {1,-1,0,0};
    public int solution(int[][] land) {
        //초기화 해주기
        int answer =0;
        srcMap = land;
        width = land[0].length;
        height = land.length;
        oilAmount = new ArrayList<Integer>();
        oilAmount.add(0);// 각 인덱스로 값을 맞춰주기 위함
        countMap = new int[height][width];
        int index = 1;
        for(int i = 0 ; i<height; i++){
            for(int j = 0; j<width; j++){
                if(land[i][j]==1 && countMap[i][j]==0){
                    count = 0;
                    makeUnique(i, j, index);
                    oilAmount.add(count);
                    index++;
                }
            }
        }
        //각 col을 순회하면서 방문표시를 초기화 해주며 석유매장량을 탐사
        for(int i= 0 ; i<width; i++){
            int sum = 0;
            visited = new boolean[oilAmount.size()];
            for(int j = 0; j<height; j++){
                int uniqueVal = countMap[j][i];
                if(!visited[uniqueVal]&&uniqueVal!=0){
                    visited[uniqueVal] = true;
                    sum+=oilAmount.get(uniqueVal);
                }
            }
            answer = Math.max(answer, sum);
        }

        return answer;
    }
    static void makeUnique(int x, int y, int unique){
        count++;
        countMap[x][y] = unique;
        for(int i =0; i<4; i++){
            int nx = x+ dx[i];
            int ny = y + dy[i];
            //맵의 범위를 벗어난다면
            if(nx<0||nx>=height||ny<0||ny>=width) continue;
            //맵에 표시된 영역이 오일부분이 아니라면
            if(srcMap[nx][ny]!=1) continue;
            //이미 방문한 오일영역이라면
            if(countMap[nx][ny]!=0)continue;
            makeUnique(nx, ny, unique);
        }
    }
}

느낀점 : 처음에는 석유 매장량을 계산하는 과정에서 맵을 복사하여 count를 하였다. 하지만, 시간초과 및 효율성 부분에서 와장창 깨졌다. 맵을 복사하지않고, 석유매장량을 count할 순 없을까? 고민하다가 듬성듬성 있는 석유 매장량 부분에 unique한 값을 부여한다면 맵을 굳이 복사하지 않더라도 각 열을 순회하면서 행방향으로 드릴해서 들어갔을 때, 방문표시만으로도 원본맵을 손상시키지 않을 수 있었다. 생각보다 오랫동안 풀이한 문제였다.