프로그래머스, 무인도 여행(python, java)

문제 설명

상하좌우로 움직이는데, 숫자로만 이어진 칸을 무인도라고 한다. 각 칸의 숫자를 구해서 오름차순 정렬후 반환하는 문제다. 만일 무인도가 없으면 -1을 반환한다.

https://school.programmers.co.kr/learn/courses/30/lessons/154540?language=python3 

프로그래머스

문제 풀이

첫 번째 접근

단순한 넓이 우선 탐색이라 금방 풀 수 있을 거라 생각했던 문제.

그러나 pair class의 row와 col을 바꿔서 써준 덕분에 예상보다 시간이 훨씬 많이 걸렸다.

 

코드

java

import java.util.*;

class pair{
    
    int row;
    int col;
    
    pair(int row, int col){
        this.col = col;
        this.row = row;
    }
}

class Solution {
    public static boolean[][] visit;
    public static int colLength, rowLength;
    public static int[] dR = {-1, 0, 1, 0}; //북동남서
    public static int[] dC = {0, 1, 0, -1};
        
    public int bfs(int r, int c, String[] map){
        Queue<pair> queue = new LinkedList<>();
        queue.add(new pair(r, c));
        visit[r][c] = true;
        int count = map[r].charAt(c)-'0';
        
        while(queue.size() != 0){
            pair current = queue.poll();
            int cR = current.row;
            int cC = current.col;
            
            for(int i=0; i<4; i++){
                int nR = cR + dR[i];
                int nC = cC + dC[i];
                
                if(nR >= 0 && nR < rowLength && nC >= 0 && nC < colLength){
                    if(map[nR].charAt(nC) != 'X' && visit[nR][nC] == false){
                        
                        visit[nR][nC] = true;
                        count += (map[nR].charAt(nC) - '0');
                        queue.add(new pair(nR, nC));
                    }
                }
            }

        }
        
        return count;
        
    }
    
    public int[] solution(String[] maps) {
        int[] answer = {};
        colLength = maps[0].length();
        rowLength = maps.length;
        visit = new boolean[rowLength][colLength];
        List<Integer> list = new ArrayList<>();
        
        for(int i=0; i<rowLength; i++){
            for(int j=0; j<colLength; j++){
                if(maps[i].charAt(j) != 'X' && visit[i][j] == false){
                    list.add(bfs(i, j, maps));
                }
            }
        }
        
        if(list.size() == 0){
            answer = new int[1];
            answer[0] = -1;
            return answer;
        }
        answer = new int[list.size()];
        Collections.sort(list);
        
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

python

from collections import deque;

def solution(maps):
    answer = []
    dR = [-1, 0, 1, 0]
    dC = [0, 1, 0, -1]
    rowLength = len(maps)
    colLength = len(maps[0])
    visit = [[False for _ in range(colLength)] for _ in range(rowLength)]
    
    def bfs(r, c, maps):
        dq = deque()
        dq.append([r, c])
        visit[r][c] = True
        count = int(maps[r][c])

        while dq:
            current = dq.popleft()
            cR = current[0]
            cC = current[1]


            for i in range(4):
                nR = cR + dR[i]
                nC = cC + dC[i]

                if 0 <= nR < rowLength and 0 <= nC <colLength:
                    if maps[nR][nC] != "X" and visit[nR][nC] == False:
                        visit[nR][nC] = True
                        count += int(maps[nR][nC])
                        dq.append([nR, nC])

        return count


    for i in range(rowLength):
        for j in range(colLength):
            if maps[i][j] != 'X' and visit[i][j] == False:
                answer.append(bfs(i, j, maps))
                
    if len(answer) == 0:
        answer.append(-1)
        return answer
    
    answer.sort()

    return answer