[Java] 무인도 여행 - Lv2 프로그래머스 DFS

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

 

풀이

---

완전탐색 문제를 처음으로 외부 검색 없이 혼자 해결한 문제... 고생의 노력이 드디어 빛을 조금 본 것 같다.

 

1. boolean타입의 이차원 배열 선언 - 해당 칸이 숫자일 경우 true처리

2. dfs메서드에서 한번 탐색이 끝나서 list.add가 되는 경우는 무인도끼리 연결이 되지 않을 때, 즉 해당 섬의 연결이 끝났을 때가 될 수 있게 조건을 줬다.

public void dfs(String[] maps, boolean[][] visited, int i, int j) {
    if(i<0 || j<0 || i>=maps.length || j>=maps[0].length()) return;
    if(maps[i].charAt(j) == 'X' || visited[i][j]) return;
    else {
        visited[i][j]=true;
        sum+=maps[i].charAt(j)-'0';
    }
    dfs(maps, visited, i+1, j);
    dfs(maps, visited, i-1, j);
    dfs(maps, visited, i, j+1);
    dfs(maps, visited, i, j-1);
}

maps의 idx를 벗어났을 경우와, 섬이 없을경우, 이미 true일 경우(섬이 존재하고, 이미 방문해서 +처리 완료) 리턴처리 해주었다.

 

3. list에 sum을 담았기 때문에, list의 사이즈가 0일 때는 문제에서 주어진 대로 answer[0]=-1인 값을 리턴해야하고, 아닐 경우 정렬하여 오름차순으로 리턴시켜주었다.

 

전체코드

class Solution {
	
    static int sum=0;
    
    public int[] solution(String[] maps) {
        List<Integer> list = new ArrayList<>();
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        for(int i=0; i<maps.length; i++) {
        	for(int j=0; j<maps[i].length(); j++) {
        		dfs(maps, visited, i, j);
        		if(sum>0) {
        			list.add(sum);
        			sum=0;
        		}
        	}
        }
        if(list.size()==0) return new int[] {-1};
        
        int[] answer = new int[list.size()];
        for(int i=0; i<answer.length; i++) {
        	answer[i]=list.get(i);
        }
        Arrays.sort(answer);
        return answer;
    }
    
    public void dfs(String[] maps, boolean[][] visited, int i, int j) {
    	if(i<0 || j<0 || i>=maps.length || j>=maps[0].length()) return;
    	if(maps[i].charAt(j) == 'X' || visited[i][j]) return;
    	else {
    		visited[i][j]=true;
    		sum+=maps[i].charAt(j)-'0';
    	}
    	dfs(maps, visited, i+1, j);
    	dfs(maps, visited, i-1, j);
    	dfs(maps, visited, i, j+1);
    	dfs(maps, visited, i, j-1);
    }
}