99클럽 코테 스터디 10일차 TIL - 익숙한 문제는 빠르게 풀기

문제 - 무인도 여행 문제링크

문제 설명

2차원 격자 maps가 주어지고, 격자는 바다를 의미하는 'X'와 1~9 사이의 숫자로 이루어져 있습니다.

해당 칸이 숫자라면 땅을 의미하고, 상하좌우로 서로 연결된 땅은 하나의 섬입니다.

maps 내의 모든 섬에 방문할 때, 각 섬에 적혀있는 모든 숫자를 다 더한 값을 담아 반환하면 됩니다.

 

풀이 과정

일반적인 BFS 섬 찾기 문제입니다. maps를 2중 for 문 순회하며 섬을 찾아 마킹하며 숫자를 더한 후 BFS가 끝나면 더한 값을 저장해 놓다가 모든 순회가 끝나면 반환하면 됩니다.

from collections import deque
def solution(maps):
    answer = []
    n = len(maps)
    m = len(maps[0])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    vis = [[False for _ in range(m)] for _ in range(n)]
    dq = deque()
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'X' or vis[i][j]:
                continue
            vis[i][j] = True
            
            dq.append((i, j))
            cnts = int(maps[i][j])
            while dq:
                x, y = dq.popleft()
                
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    
                    if nx < 0 or nx >= n or ny < 0 or ny >= m:
                        continue
                    if maps[nx][ny] == 'X' or vis[nx][ny:
                        continue

                    vis[nx][ny] = True
                    cnts += int(maps[nx][ny])
                    dq.append((nx, ny))
            answer.append(cnts)
            
    if answer:
        answer.sort()
        return answer
    return [-1]

 

Java 코테 연습을 할겸 Java로도 풀어보았습니다.

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        List<Integer> lst = new ArrayList<>();
        int n = maps.length;
        int m = maps[0].length();
        boolean[][] vis = new boolean[n][m];
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maps[i].charAt(j) == 'X' || vis[i][j]) {
                    continue;
                }
                lst.add(bfs(maps, vis, i, j, dx, dy));
            }
        }

        Collections.sort(lst);
        if (lst.isEmpty()) {
            return new int[] {-1};
        }

        return lst.stream().mapToInt(Integer::intValue).toArray();
    }

    private int bfs(String[] maps, boolean[][] vis, int x, int y, int[] dx, int[] dy) {
        int n = maps.length;
        int m = maps[0].length();
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {x, y});
        vis[x][y] = true;
        int sum = maps[x].charAt(y) - '0';

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0], cy = cur[1];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maps[nx].charAt(ny) == 'X' || vis[nx][ny]) {
                    continue;
                }

                vis[nx][ny] = true;
                q.offer(new int[] {nx, ny});
                sum += maps[nx].charAt(ny) - '0';
            }
        }

        return sum;
    }
}

역시 파이썬보다 자바가 코드량이 훨씬 깁니다.

 

maps를 인덱스 접근할 때도 maps[i][j] 이렇게 하니 에러가 발생했습니다. maps는 String으로 이루어진 array이기 때문에 첫항은 []로 접근이 가능하지만, String은 charAt()으로 접근할 수 있기 때문입니다.

 

그리고 char타입을 int로 타입캐스팅하면 아스키코드 값이 반환되기 때문에, '6'과 같은 문자에서 6을 추출하기 위해서는 '6' - '0'같이 아스키코드 차이를 얻는 방법이 있습니다.

 

자바는 타입도 신경을 써줘야 해서 List로 받고 다시 반환타입인 int[]로 바꿔주는 작업이 필요했습니다.

lst.stream(lst).mapToInt(Integer::intValue).toArray();

위 코드로 바꿔줄 수 있는데 너무 깁니다..

파이썬 코드에서 사용하는 deque를 자바에서 대체할 자료구조는 LinkedList, ArrayDeque가 있습니다.

ArrayDeque이 양끝단 삽입삭제를 O(1)에 수행할 수 있기 때문에 더 효율적입니다.

 

총평

자바 코테 연습을 꾸준히 하자.