[프로그래머스] 레벨2 무인도 여행

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

프로그래머스

 

전형적인 그래프 탐색 문제이다. 일단 입력값의 범위가 2차원 배열이고, 최대가 100 * 100이므로 시간복잡도에 대해서는 크게 신경쓰지 않아도 된다고 생각했기 때문에 Queue를 이용한 BFS 방식을 통해 문제를 해결했다.

한 가지 예외처리할 부분은 모든 map 입력값이 전부 'X'일 경우(섬일경우)인데, 이 경우에는 애초에 list에 어떤 값도 들어가지 않으므로 쉽게 예외처리할 수 있었고, 그 외의 경우에는 Collection 라이브러리를 사용해 sort해서 리턴해주면 되는 문제였다.

---

문제 및 입출력

---

입출력 예시

---

코드

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

class Solution
{
    static int[][] dir = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    
    public static void traverse(char[][] map, int[] start, int maxX, int maxY, LinkedList<Integer> list)
    {
        Queue<int[]> q = new LinkedList<int[]>();
        q.add(new int[]{start[0], start[1]});
        int sum = 0;
        sum += map[start[0]][start[1]] - '0';
        map[start[0]][start[1]] = 'X';
        
        while(!q.isEmpty())
        {
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            
            for(int i=0; i<dir.length; i++)
            {
                x += dir[i][0];
                y += dir[i][1];
                
                if(x>=0 && x<maxX && y>=0 && y<maxY && map[x][y]!='X')
                {
                    q.add(new int[]{x,y});
                    sum += map[x][y] - '0';
                    map[x][y] = 'X';
                }
                
                x -= dir[i][0];
                y -= dir[i][1];
            }
        }
        
        list.add(sum);
    }
    public static Object[] solution(String[] maps)
    {
        char[][] map = new char[maps.length][maps[0].length()];
        LinkedList<Integer> list = new LinkedList<Integer>();
        
        for(int i=0; i<maps.length; i++)
        {
            map[i] = maps[i].toCharArray();
        }
        for(int i=0; i<map.length; i++)
        {
            for(int j=0; j<map[0].length; j++)
            {
                if(map[i][j]!='X')
                {
                    traverse(map, new int[]{i,j}, map.length, map[i].length, list);
                }
            }
        }
        
        if(list.isEmpty())
        {
            return new Object[]{-1};
        }
        
        Collections.sort(list);
        return list.toArray();
    }
}