간만에 간단한 BFS 문제입니다.
맨첨에 색깔이 같으면 같은 영역이라고 생각했는데 그것도 아니고 그냥 따로 봐주면 돼서 더 간단합니다.
import java.util.*;
class Solution {
static class Dir {
int y, x;
Dir(int y, int x) {
this.y = y;
this.x = x;
}
}
int[] dy = { 1, -1, 0, 0 };
int[] dx = { 0, 0, 1, -1 };
boolean[][] v;
int[][] p;
int M, N;
public int[] solution(int m, int n, int[][] picture) {
M = m; N = n;
p = picture;
v = new boolean[m][n];
int[] answer = new int[2];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(v[i][j] == true) continue;
int color = p[i][j];
if(color != 0) {
answer[0]++;
answer[1] = Math.max(answer[1], bfs(new Dir(i, j), color));
}
}
}
return answer;
}
public int bfs(Dir start, int color) {
Queue<Dir> q = new LinkedList<>();
int cnt = 1;
q.offer(start);
v[start.y][start.x] = true;
while (!q.isEmpty()) {
Dir cur = q.poll();
for (int i = 0; i < 4; i++) {
Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
if (!isIn(next) || p[next.y][next.x] != color || v[next.y][next.x] == true) continue;
v[next.y][next.x] = true;
q.offer(next);
cnt++;
}
}
return cnt;
}
public boolean isIn(Dir c) {
if (0 <= c.y && c.y < M && 0 <= c.x && c.x < N) return true;
else return false;
}
}
험 일단 m, n, picture를 다른 메소드에서도 쓰려고 파라미터로 안 넘기고 전역변수를 선언해서 썼습니다.
로직은 뭐 간단합니다!! 눈감고 물구나무서서도 짤 수 있을 정도
m * n 을 돌면서 picture[i][j] 가 0인거 제끼고 안에서 bfs를 돌려서 그 영역의 넓이를 구해주면 됩니다. 이때 최대 넓이를 구해야 하므로 최댓값을 갱신해주고, picture[i][j]가 0이 아닐때마다 영역의 개수++ 해주면 되는 것이지요..
감사합니다!!!
'Algorithm > Programmers' 카테고리의 다른 글
[2021 카카오 채용연계형 인턴십][문자열 처리] 숫자 문자열과 영단어 - Java (0) | 2021.07.13 |
---|---|
[완전 탐색/소수 판별] 소수 찾기 - Java (0) | 2020.12.15 |
[2019 카카오 개발자 겨울 인턴십][이분 탐색(Parametric Search)] 징검다리 건너기 - Java (0) | 2020.12.14 |
[Trie] 전화번호 목록 - Java (1) | 2020.12.13 |
[2019 카카오 개발자 겨울 인턴십][Map 활용/DFS] 호텔 방 배정 - Java (0) | 2020.12.13 |