https://school.programmers.co.kr/learn/courses/30/lessons/154540
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 풀이]
- bfs를 이용해 상하좌우 인접한 땅을 찾습니다.
- 무인도로 이루어진 숫자의 합을 ArrayList에 추가
- bfs가 끝나면 ArrayList를 오름차순 정렬 시켜줍니다.
- ArrayList 크기가 0이면 -1을 넣어준후 리턴 시켜주면 됩니다.
[java]
mport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
static int dx[] = {0, 0, -1, 1};
static int dy[] = {-1, 1, 0, 0};
static boolean visited[][];
static char[][] map;
static ArrayList<Integer> answer = new ArrayList<>();
public Integer[] solution(String[] maps) {
visited = new boolean[maps.length][maps[0].length()];
map = new char[maps.length][maps[0].length()];
for(int i=0; i<maps.length; i++){
for(int j=0; j<maps[0].length(); j++){
map[i][j] = maps[i].charAt(j);
}
}
for(int i=0; i<maps.length; i++){
for(int j=0; j<maps[0].length(); j++){
if(!visited[i][j] && maps[i].charAt(j) != 'X'){
bfs(new Pos(i, j));
}
}
}
Collections.sort(answer);
if(answer.size() == 0) answer.add(-1);
return answer.toArray(new Integer[0]);
}
public static void bfs(Pos start){
Queue<Pos> q = new LinkedList<>();
q.add(start);
visited[start.y][start.x] = true;
int sum = 0;
while(!q.isEmpty()){
Pos cur = q.poll();
sum += map[cur.y][cur.x] - '0';
for(int i=0; i<4; i++){
int ny = cur.y + dy[i];
int nx = cur.x + dx[i];
if(check(ny,nx) && !visited[ny][nx]){
q.add(new Pos(ny,nx));
visited[ny][nx] = true;
}
}
}
answer.add(sum);
}
public static boolean check(int ny, int nx){
return (ny >=0 && ny < map.length && nx >=0 && nx <map[0].length
&& map[ny][nx] != 'X') ? true : false;
}
}
class Pos{
int x, y;
public Pos(int y, int x) {
this.x = x;
this.y = y;
}
}
'PS > programmers' 카테고리의 다른 글
[프로그래머스] - 미로탈출 (0) | 2023.02.16 |
---|---|
[프로그래머스] - 소수찾기 (0) | 2023.02.10 |
프로그래머스 - 개인정보 수집 유효기간 (0) | 2023.01.18 |
프로그래머스 - 프렌즈 4블록 (0) | 2022.08.30 |
Programmers - 피로도 (Java) 완전탐색 (0) | 2022.08.10 |