[프로그래머스] Lv.2 무인도 여행JAVA 풀이
문제 Lv.2 무인도 여행
: 지도 = 1 x 1 크기의 사각형으로 이루어진 직사각형 격자 형태
격자 구성 = X, 숫자 (1 ~ 9)
- X = 바다
- 숫자 = 무인도 (상, 하, 좌, 우 붙어있는 애들은 하나의 무인도, 대각선은 다른땅)
: 하나의 무인도 숫자 합 = 해당 무인도에서 최대로 머무를 수 있는 기한 (오름차순으로 출력)
무인도가 없는 경우 = -1 출력
: maps = 지도 (문자열 배열)
[지도 배열 예시]
[알고 가기]
< DFS >
- 깊이 우선 탐색
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 or 재귀함수 이용
- 제일 깊게 내려간 뒤 더이상 갈 수 없을 때 옆으로
이동해서 다시 깊게 내려가기를 반복
- 구현 : DFS (간단) > BFS
- 검색 속도 : BFS > DFS (느림)
출처 https://developer-mac.tistory.com/64
[코드]
import java.util.*;
class Solution {
static int X = 0;
static int Y = 0;
static int day = 0;
public int[] solution(String[] maps) {
X = maps.length;
Y = maps[0].length();
int[][] map = new int[X][Y];
for(int i = 0; i < X; i++) {
char[] c = maps[i].toCharArray();
for(int j = 0; j < c.length; j++) {
if(c[j] == 'X') {
map[i][j] = 0;
} else {
map[i][j] = c[j] - '0';
}
}
}
List<Integer> days = new ArrayList<>();
boolean[][] visited = new boolean[X][Y];
for(int i = 0; i < X; i++) {
for(int j = 0; j < Y; j++) {
if(!visited[i][j] && map[i][j] > 0) {
dfs(map, visited, i, j);
days.add(day);
day = 0;
}
}
}
if(days.isEmpty()) {
return new int[]{-1};
}
Collections.sort(days);
int[] answer = new int[days.size()];
for(int i = 0; i < answer.length; i++) {
answer[i] = days.get(i);
}
return answer;
}
private void dfs(int[][] map, boolean[][] visited, int x, int y) {
day += map[x][y];
visited[x][y] = true;
int[] upAndDown = {1, -1, 0, 0};
int[] leftAndRight = {0, 0, 1, -1};
for(int i = 0; i < 4; i++) {
int newX = x + upAndDown[i];
int newY = y + leftAndRight[i];
if(newX < 0 || newY < 0 || newX >= X || newY >= Y) {
continue;
}
if(!visited[newX][newY] && map[newX][newY] > 0) {
dfs(map, visited, newX, newY);
}
}
}
}
: static int X = 0;
static int Y = 0;
static int day = 0;
: public int[] solution(String[] maps) { 2차원 배열 만들기
X = maps.length;
Y = maps[0].length();
int[][] map = new int[X][Y];
: for(int i = 0; i < X; i++) { X부터 시작
char[] c = maps[i].toCharArray(); 문자 하나씩 뜯어보기
for(int j = 0; j < c.length; j++) {
if(c[j] == 'X') { 문자가 X와 같다면
map[i][j] = 0; 2차원 배열에 0으로 등록
} else { 아닐 경우
map[i][j] = c[j] - '0'; 문자에서 - 0
}
}
}
: List<Integer> days = new ArrayList<>(); List 사용
boolean[][] visited = new boolean[X][Y]; boolean[][] visited
for(int i = 0; i < X; i++) { X부터 시작
for(int j = 0; j < Y; j++) { Y도 시작
if(!visited[i][j] && map[i][j] > 0) { 방문한 적이 없고, 무인도일 경우
dfs(map, visited, i, j); dfs 설정
days.add(day); day 추가
day = 0; day 0으로 초기설정
}
}
}
: if(days.isEmpty()) { 무인도 없는 경우는 -1 출력
return new int[]{-1};
}
: Collections.sort(days); 오름차순 정렬
int[] answer = new int[days.size()];
for(int i = 0; i < answer.length; i++) {
answer[i] = days.get(i);
}
return answer;
}
: private void dfs(int[][] map, boolean[][] visited, int x, int y) { 머무를 수 있는 날짜 계산
day += map[x][y]; 해당 위치에서의 값으로 day 갱신
visited[x][y] = true;
int[] upAndDown = {1, -1, 0, 0}; 상, 하
int[] leftAndRight = {0, 0, 1, -1}; 좌, 우
: for(int i = 0; i < 4; i++) {
int newX = x + upAndDown[i];
int newY = y + leftAndRight[i];
if(newX < 0 || newY < 0 || newX >= X || newY >= Y) { 범위 확인
continue;
}
if(!visited[newX][newY] && map[newX][newY] > 0) { 방문한 적이 없고 무인도일 경우
dfs(map, visited, newX, newY); dfs
}
}
https://school.programmers.co.kr/learn/courses/30/lessons/154540
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr