자바칩
[프로그래머스 / Java] PCCP 기출문제 2번: 석유 시추 (BFS) 본문
난이도: Level 2
문제: https://school.programmers.co.kr/learn/courses/30/lessons/250136
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
제한시간 안내
- 정확성 테스트 : 10초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
쉬운 문제인데 이 문제는 효율성까지 같이 체크해서 효율성 테스트를 통과하기까지에는 1시간정도 걸렸다.
참고로 프로그래머스는
class Solution {
public int solution(들어오는 데이터) {
int answer = 0;
return answer;
}
}
이런 식으로 되어 있다.
먼저 Solution 클래스의 인스턴스 변수로 다음과 같이 선언해준다.
solution 메서드에서 인스턴스 변수를 초기화해준다.
area 배열은 입력 데이터로 들어오는 land 배열에 해당하는 석유 덩어리들의 구역을 나눠주는 배열이다.
만약 land 배열이 이렇다면, 석유 덩어리는 총 3개가 된다.
area 배열은 이렇게 각각의 석유 덩어리들의 구역 번호를 부여하는 역할을 해준다.
위와 같이 area 배열에 구역 번호를 부여하는 역할을 하는 코드는 다음과 같다.
방문하지 않은 석유 칸을 찾으면 새로운 석유 덩어리를 찾았다는 것이므로, 석유 덩어리의 크기를 구하고 구역 번호를 부여하기 위해서 findOilLump 메서드의 매개변수로 구역 번호도 같이 넘겨주고, 다음 석유 덩어리의 번호 부여를 위해서 구역 번호는 1 증가시킨다.
findOilLump 메서드는 주어진 land 배열에서 석유가 있는 칸(1)을 모두 석유 덩어리의 크기로 바꿔준다.
만약 어떤 석유의 덩어리의 크기가 7이라면, 그 칸에 해당하는 석유들의 칸을 모두 원래 값이었던 1에서 7로 바꿔준다.
이제 findOilLump 메서드의 구현을 보자.
여기서 Oil 클래스가 나오는데, Oil 정적 멤버 클래스는 다음과 같다.
다른 로직은 일반 bfs와 비슷한데, 효율성 테스트를 통과하기 위해서 석유 리스트를 선언했다.
이 findOilLump 메서드를 수행하는 동안은 모두 같은 석유 덩어리에 속하기 때문에, 여기에 속하는 석유들을 모두 이 리스트에 추가하면 된다.
while 문을 빠져나오고(석유 덩어리에 해당하는 모든 칸을 탐색하고), 리스트에 속해있는 모든 석유들의 land 칸을 이 덩어리의 최종 크기로 바꿔준다.
초기 land 배열에 있던 1 값들을 모두 석유 덩어리의 크기로 바꿔줬고, 석유 덩어리의 구역 번호도 나누어 주었다.
최종적으로 모든 열에서 석유를 뽑아서 그 최댓값을 찾아서 리턴을 하면 된다.
열부터 탐색하는 이유는
(0, 0), (1, 0), (2, 0), ..., (n - 1, 0)
...
(n - 1, 0), (n - 1, 0), ..., (n - 1, m - 1)
순서로 탐색하기 위해서이다.
하나의 열을 기준으로 행을 계속 탐색하는 것이다.
여기서 구역 번호들의 집합인 Set을 사용했다.
하나의 열에 해당하는 모든 열을 탐색하면서 석유가 있는 칸을 발견하면 sum 변수에 더하는데, 같은 구역에 속한 석유는 중복해서 더하면 안되기 때문이다.
예를 들면 다음과 같다.
위의 보라색 동그라미가 있는 열을 보면 석유가 모두 같은 구역에 속해있다.
7을 굳이 중복해서 더할 필요 없이, 딱 한 번만 더하고 해당 구역 번호를 저 areaNums 집합에 추가를 하면,
그 이후에 찾는 칸은 areaNums에 있는 구역 번호인지 확인하고, 없으면 더하는 식의 로직을 수행한다.
여기에서는 보라색 동그라미가 있는 열을 보면 둘의 구역 번호는 다르므로 7을 더하고, 이후에 2를 더한다.
백준으로 풀다가 프로그래머스로 바꾼 이유는 IDE가 없는 환경에서의 연습과 인풋 데이터를 처리할 때 버벅거리지 않도록 연습하기 위해서다.
코딩테스트는 대부분 프로그래머스에서 실행이 된다.
백준에서는 그냥 텍스트로 주어진 인풋 데이터를 처리하면 되는데, 프로그래머스는 인풋 데이터를 매개변수로 주기 때문에 이것을 처리하는 것이 생각보다 매끄럽게 되지 않을 수가 있다.
누군가는 입출력을 직접 처리하지 않아도 돼서 더 편하다고 생각할 수도 있겠지만 나는 입출력 처리에 익숙해져서 그런지 오히려 불편하다.
그리고 IDE에서 코딩을 하면 문법에 맞지 않는 코드를 잘못 칠 때마다 컴파일 에러를 자동으로 알려주는데, 프로그래머스는 직접 실행을 해야 컴파일 에러 메시지를 알려준다. 이것 때문에 좀 멘탈이 더 터지게 된다.
이런 복합적인 이유로 백준으로만 연습하다가 프로그래머스에서 코딩 테스트를 보게 되면 예상했던 대로 되지가 않아서 더 심리적으로 불안하고 압박감을 가지고 보게 된다.
프로그래머스 환경에 좀 익숙해져야겠다.
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
import java.util.*;
class Solution {
int[] dx = {-1, 1, 0, 0}; // 상(-1, 0), 하(1, 0),
int[] dy = {0, 0, -1, 1}; // 좌(0, -1), 우(0, 1) 이동
int n, m;
boolean[][] visited;
int[][] area;
public int solution(int[][] land) {
int answer = 0; // 시추관 하나로 뽑을 수 있는 가장 많은 석유량
n = land.length; // 땅의 세로 길이
m = land[0].length; // 땅의 가로 길이
visited = new boolean[n][m]; // 방문 체크 배열
area = new int[n][m]; // 각 구역마다 번호 부여하는 배열
int areaNum = 1; // 구역 번호
// 모든 칸을 탐색
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
// 해당 칸을 방문하지 않았고, 석유가 있는 칸이라면
if (!visited[x][y] && land[x][y] == 1) {
// 석유 덩어리의 크기를 구하고, 구역 번호를 부여하기
findOilLump(land, x, y, areaNum++);
}
}
}
// 열을 기준으로 탐색
for (int y = 0; y < m; y++) {
int sum = 0; // 해당 열에서 뽑은 석유량
// 해당 열에서 뽑을 수 있는 석유 덩어리의 구역 번호들의 집합
Set<Integer> areaNums = new HashSet<>();
// 해당 열의 모든 행을 탐색
for (int x = 0; x < n; x++) {
// 해당 칸에 석유가 존재하고,
// 구역 번호 집합에 해당 석유의 구역 번호가 없다면
// 새로운 석유 덩어리를 발견한 것
if (land[x][y] != 0 && !areaNums.contains(area[x][y])) {
sum += land[x][y]; // 뽑은 석유 덩어리의 크기를 누적
areaNums.add(area[x][y]); // 구역 번호 집합에 해당 석유의 구역 번호 추가
}
}
answer = Math.max(answer, sum); // 하나의 열에서 뽑을 수 있는 석유량의 최댓값 갱신
}
return answer; // 시추관 하나로 뽑을 수 있는 가장 많은 석유량 리턴
}
// 석유 덩어리의 크기를 구하고, 구역 번호를 부여하는 메서드
public void findOilLump(int[][] land, int startX, int startY, int areaNum) {
Queue<Oil> queue = new LinkedList<>(); // bfs 수행을 위한 큐
List<Oil> oils = new ArrayList<>(); // 석유 덩어리에 해당하는 석유 칸들의 리스트
int count = 1; // 석유 덩어리에 해당하는 석유 칸들의 개수
Oil start = new Oil(startX, startY); // 시작 석유 생성
queue.add(start); // 시작 석유를 큐에 삽입
visited[startX][startY] = true; // 시작 석유를 방문 체크
oils.add(start); // 석유 리스트에 시작 석유 추가
land[startX][startY] = count++; // 현재 석유 칸의 개수를 시작 칸에 저장하고 석유 칸의 개수 1 증가
area[startX][startY] = areaNum; // 현재 구역 번호를 시작 칸에 부여
// 큐가 빌 때까지 반복
while (!queue.isEmpty()) {
Oil now = queue.poll(); // 현재 석유를 큐에서 뽑기
// 현재 석유를 기준으로 상, 하, 좌, 우 탐색
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i]; // 인접 칸의 x좌표
int ny = now.y + dy[i]; // 인접 칸의 y좌표
// 인접 칸의 인덱스가 유효하지 않다면 건너뛰기
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
// 인접 칸을 이미 방문했거나, 석유가 없는 칸이라면 건너뛰기
if (visited[nx][ny] || land[nx][ny] == 0) {
continue;
}
Oil next = new Oil(nx, ny); // 인접 석유 생성
queue.add(next); // 인접 석유를 큐에 삽입
visited[nx][ny] = true; // 인접 석유를 방문 체크
oils.add(next); // 석유 리스트에 인접 석유 추가
land[nx][ny] = count++; // 현재 석유 칸의 개수를 인접 칸에 저장하고 석유 칸의 개수 1 증가
area[nx][ny] = areaNum; // 현재 구역 번호를 인접 칸에 부여
startX = nx; // 가장 최근에 방문한 x좌표 갱신
startY = ny; // 가장 최근에 방문한 y좌표 갱신
}
}
// 이 석유 덩어리에 해당하는 모든 석유를 탐색
for (Oil oil : oils) {
// 리스트에 있는 석유 칸들을 이 석유 덩어리의 최종 크기로 모두 바꿔주기
land[oil.x][oil.y] = land[startX][startY];
}
}
static class Oil {
int x, y; // 석유의 x좌표, y좌표
Oil(int x, int y) {
this.x = x;
this.y = y;
}
}
}
|
cs |
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스 / Java] 코딩테스트 연습: 디스크 컨트롤러 (힙) (0) | 2024.08.22 |
|---|---|
| [프로그래머스 / Java] 코딩테스트 연습: H-Index (정렬) (0) | 2024.08.11 |
| [프로그래머스 / Java] 코딩테스트 연습: 가장 큰 수 (정렬) (0) | 2024.08.11 |
| [프로그래머스 / Java] 코딩테스트 연습: 베스트앨범 (해시) (0) | 2024.08.09 |
| [프로그래머스 / Java] 코딩테스트 연습: 의상 (해시) (0) | 2024.08.08 |