[코드트리 챌린지] 숫자가 가장 큰 인접한 곳으로 동시에 이동

코드트리 5주 차 블로그챌린지입니다

저는 기업별 커리큘럼을 신청하였고 오늘은 삼성 커리큘럼을 풀어 보았습니다

숫자가 가장 큰 인접한 곳으로 동시에 이동 문제를 리뷰해보고자 합니다

https://www.codetree.ai/missions/13/problems/move-to-max-adjacent-cell-simultaneously/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

풀이방법

• 구슬이 상하좌우 방향으로 움직이는데 가장 큰 숫자가 있는 위치로 이동한다
• 가장 큰 숫자가 여러개라면 상하좌우 우선순위를 두고 이동한다
  • 우좌하상 순서대로 순회하면서 최댓값으로 이동하면 된다
• 이동 후 2개 이상의 구슬이 있다면 충돌이 일어난 것으로 모두 사라진다
  • 이동 후 위치가 겹치는지 확인해야하기 때문에 이를 확인하기 위한 자료구조를 사용해야한다
  • 저는 풀이에서 Set을 이용했고, 해설에서는 visited와 같은 배열을 만들어놓고 count를 센다

import java.util.*;
import java.io.*;

public class Main {
    public static int[][] map, direction = {{0,1},{0,-1},{1,0},{-1,0}};
    public static int n, MAX_LEN = 21;
    public static Queue<int[]> queue = new ArrayDeque<>();
    public static void main(String[] args) throws IOException{
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken()), t = Integer.parseInt(st.nextToken());
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken())-1, c = Integer.parseInt(st.nextToken())-1;
            queue.offer(new int[]{r, c});
        }
        for(int i=0; i<t; i++) {
            move();
        }
        System.out.print(queue.size());
        br.close();
    }

    public static void move() {
        Set<Integer> set = new HashSet<>(), removes = new HashSet<>();
        int size = queue.size();
        for(int i=0; i<size; i++) {
            int[] pos = queue.poll();

            int r=0, c=0, max = -1;
            for(int j=0; j<direction.length; j++) {
                int nextR = pos[0] + direction[j][0];
                int nextC = pos[1] + direction[j][1];
                if(isRange(nextR, nextC) && map[nextR][nextC] >= max) {
                    r = nextR;
                    c = nextC;
                    max = map[r][c];
                }
            }
            int key = r*MAX_LEN + c;
            if(set.contains(key)) removes.add(key);
            set.add(key);
            queue.offer(new int[]{r, c});
        }
        size = queue.size();
        for(int i=0; i<size; i++) {
            int[] pos = queue.poll();
            if(removes.contains(pos[0]*MAX_LEN + pos[1])) continue;
            queue.offer(pos);
        }
    }

    public static boolean isRange(int r, int c) {
        return r>=0 && r<n && c>=0 && c<n;
    }
}

count 배열을 사용하게 되면 코드가 조금 더 간결해질 수 있다

public static void move() {
		while (!queue.isEmpty()) {
            int[] pos = queue.poll();

            int r=0, c=0, max = -1;
            for(int j=0; j<direction.length; j++) {
                int nextR = pos[0] + direction[j][0];
                int nextC = pos[1] + direction[j][1];
                if(isRange(nextR, nextC) && map[nextR][nextC] >= max) {
                    r = nextR;
                    c = nextC;
                    max = map[r][c];
                }
            }
            count[r][c]++;
        }
        
        for(int i=0; i<n; i++) {
        	for(int j=0; j<n; j++) {
            	if(count[i][j] == 1) queue.offer(new int[]{i, j});
            }
        }
    }

공간복잡도가 증가한다고 생각하여 자료구조를 활용했던건데 결과를보면 시간이나 메모리나 다른 풀이에 비해 높게 나왔다