csct3434
[level 2] [PCCP 기출문제] 2번 / 석유 시추 - 250136 본문
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class Solution {
private Map<Integer, Integer> countsPerSector = new HashMap<>();
private int[][] sectorInfo;
private boolean[][] visited;
public int solution(int[][] land) {
int answer = 0;
int rows = land.length;
int cols = land[0].length;
sectorInfo = new int[rows][cols];
visited = new boolean[rows][cols];
int sectorNumber = 1;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (land[row][col] == 1 && sectorInfo[row][col] == 0) {
bfs(land, rows, cols, row, col, sectorNumber++);
}
}
}
for (int col = 0; col < cols; col++) {
int totalCount = 0;
HashSet<Integer> visitedSector = new HashSet<>();
for (int row = 0; row < rows; row++) {
int sector = sectorInfo[row][col];
if (land[row][col] == 1 && !visitedSector.contains(sector)) {
totalCount += countsPerSector.get(sector);
visitedSector.add(sector);
}
}
answer = Math.max(answer, totalCount);
}
return answer;
}
private void bfs(int[][] land, int rows, int cols, int row, int col, int sectorNumber) {
Queue<Matrix> queue = new LinkedList<>();
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
int count = 0;
visited[row][col] = true;
sectorInfo[row][col] = sectorNumber;
queue.add(new Matrix(row, col));
while (!queue.isEmpty()) {
count++;
Matrix matrix = queue.poll();
int x = matrix.row;
int y = matrix.col;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!(nx >= 0 && nx < rows && ny >= 0 && ny < cols)) {
continue;
}
if (!visited[nx][ny] && land[nx][ny] == 1) {
queue.add(new Matrix(nx, ny));
visited[nx][ny] = true;
sectorInfo[nx][ny] = sectorNumber;
}
}
}
countsPerSector.put(sectorNumber, count);
}
private static class Matrix {
int row;
int col;
public Matrix(int row, int col) {
this.row = row;
this.col = col;
}
}
}
'프로그래머스' 카테고리의 다른 글
[level 2] 롤케이크 자르기 - 132265 (1) | 2024.02.29 |
---|---|
[level 2] 귤 고르기 - 138476 (0) | 2024.02.29 |
[level 2] 요격 시스템 - 181188 (0) | 2024.02.29 |
[level 2] 과제 진행하기 - 176962 (0) | 2024.02.29 |
[level 2] 이모티콘 할인행사 - 150368 (0) | 2024.02.29 |