[프로그래머스] PCCP 기출문제 2번 석유 시추 (LV.2/JAVA)

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

 

문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

 

0	0	0	1	1	1	0	0
0	0	0	0	1	1	0	0
1	1	0	0	0	1	1	0
1	1	1	0	0	0	0	0
1	1	1	0	0	0	1	1

 

시추관의 위치	획득한 덩어리	총 석유량
1	8	8
2	8	8
3	8	8
4	7	7
5	7	7
6	7	7
7	7, 2	9
8	2	2

 

 

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

 

 

제한시간 안내
정확성 테스트 : 10초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

 

 

1차 풀이

import java.util.*;

class Solution {
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[][] map;
	static int M, N;

    public int solution(int[][] land) {
        int answer = 0;
		map = land;
		
		M = land.length;
		N = land[0].length;
		
		List<Integer> result = new ArrayList<>();
		
		for (int x=0; x<N; x++) {
			int sum = 0;
			boolean[][] visited = new boolean[M][N];
		
			for (int y=0; y<M; y++) {
				sum += dfs(x, y, visited);
			}
			
			result.add(sum);
		}
		
		Collections.sort(result, Collections.reverseOrder());
		
        return result.get(0).intValue();
    }
	
	private int dfs(int x, int y, boolean[][] visited) {
		if (map[y][x] == 0 || visited[y][x]) {
			return 0;
		}
		
		int sum = map[y][x];
		visited[y][x] = true;
		
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
				if (!visited[ny][nx] && map[ny][nx] != 0) {
					sum += dfs(nx, ny, visited);
				}
			}
		}
		return sum;
	}
}

 

DFS를 선택하여 재귀함수로 구현하였습니다.

정확성 면에서는 이렇게 해도 답은 맞지만 영 껄끄러운 마음과 함께 당연하게도 효율성 테스트가 실패했네요.

아무리 생각해도 이미 방문한 곳을 또 방문하는 형태는 효율적이지 않습니다...

어떻게 할까 고민하다가 방문한 x값을 hashSet에 넣어준 후에, 이미 방문한 칸은 다시 방문하지 않는 방향으로 코드를 수정하였습니다.

 

 

2차 풀이

import java.util.*;

class Solution {
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static boolean[][] visited;
	static int[][] map;
	static int M, N;
	static HashMap<Integer, Integer> hm = new HashMap<>();

    public int solution(int[][] land) {
        int answer = 0;
		map = land;
		
		M = land.length;
		N = land[0].length;
		visited = new boolean[M][N];
		
		for (int x=0; x<N; x++) {
			for (int y=0; y<M; y++) {
				if(!visited[y][x] && map[y][x] != 0) {
					HashSet<Integer> hs = new HashSet<>();
					int sum = 0;
					sum += dfs(x, y, hs);
					setValue(hs, sum);
				}
			}
		}
		
		ArrayList<Integer> result = new ArrayList<>(hm.values());
		Collections.sort(result, Collections.reverseOrder());
		
        return result.get(0).intValue();
    }
	
	private int dfs(int x, int y, HashSet hs) {
		int sum = map[y][x];
		visited[y][x] = true;
		hs.add(x);
		
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
				if (!visited[ny][nx] && map[ny][nx] != 0) {
					sum += dfs(nx, ny, hs);
				}
			}
		}
		return sum;
	}
	
	private void setValue(HashSet<Integer> hs, int value) {
		for (Integer i : hs) {
			hm.put(i, hm.getOrDefault(i, 0)+value);
		}
	}
}

 

잘 해결되는가 하더니....

테스트케이스 5번에서 런타임 에러가 떨어지길래 질문을 확인해 봤습니다.

 

https://school.programmers.co.kr/questions/81022

 

1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500

 

제한조건에서 최댓값이 500*500이라 스택오버플로우....?

아무래도 DFS, BFS 둘 다 풀 수 있어 보이는 문제라면 BFS로 푸는 게 효율성을 통과하기 쉬워보입니다.

 

기본 로직은 동일하게 가져가면서 BFS로만 변경했습니다. 😂

DFS가 구현이 쉽긴한데 앞으로 제한조건을 보고 결정해야겠습니다..

 

 

3차 풀이

import java.util.*;

class Solution {
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static boolean[][] visited;
	static int M, N;
	static HashMap<Integer, Integer> hm = new HashMap<>();

    public int solution(int[][] land) {
		M = land.length;
		N = land[0].length;
		visited = new boolean[M][N];
		
		for (int x=0; x<N; x++) {	
			for (int y=0; y<M; y++) {
				if (!visited[y][x] && land[y][x] == 1) {
					bfs(land, x, y);
				}
			}
		}
		
		ArrayList<Integer> result = new ArrayList<>(hm.values());
		Collections.sort(result, Collections.reverseOrder());
		
        return result.get(0).intValue();
	}
	
	private void bfs(int[][] land, int x, int y) {
		Queue<Pos> que = new LinkedList<>();
		que.add(new Pos(x, y));
		visited[y][x] = true;
		
		int sum = 0;
		
		HashSet<Integer> hs = new HashSet<>();
		hs.add(x);

		
		while (!que.isEmpty()) {
			Pos now = que.poll();
			sum++;
			
			for (int i=0; i<4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				
				if (!(nx >= 0 && nx < N && ny >= 0 && ny < M)) continue;
				if (land[ny][nx] != 1) continue;
				if (visited[ny][nx]) continue;
				
				visited[ny][nx] = true;
				que.add(new Pos(nx, ny));
				hs.add(nx);
			}
		}
		
		for (Integer i : hs) {
			hm.put(i, hm.getOrDefault(i, 0)+sum);
		}
	}
	
	private static class Pos {
        int x;
        int y;

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