🔗 문제 링크


📝 문제 설명

이 문제는 R×C 크기의 격자 위에서 진행됩니다.
격자에는 나의 로봇("I")과 상대 로봇들("R")이 배치되어 있으며,
주어진 이동 명령에 따라 나의 로봇이 이동할 때마다 상대 로봇들은
나의 로봇을 향해 그리디하게 한 칸씩 이동합니다. 🤖➡️

특히, 상대 로봇이 같은 칸에 여러 개 모이면 모두 제거되고,
만약 나의 로봇이 상대 로봇과 같은 칸으로 이동하면 게임 오버가 됩니다. ❌

문제의 목표는 이동 명령을 모두 수행한 후의 최종 격자 상태를 출력하거나,
중간에 나의 로봇이 잡혔을 경우 "kraj <순서>"를 출력하는 것입니다.


✅ 접근 방식 및 시도한 방법들

1️⃣ 원래 구현 (문자열 처리, HashMap, Queue 사용)

  • 구현 내용:
    • Queue를 사용하여 상대 로봇(arduino)의 위치를 관리합니다.
    • 각 이동마다 모든 상대 로봇에 대해 9방향(현재 위치 포함)으로 이동할 후보를 평가하고,
      나의 로봇과의 거리를 기준으로 최적의 방향을 선택합니다.
  • 충돌 처리:
    • 이동 후, 각 로봇의 위치를 문자열로 표현하여 HashMap에 기록한 뒤,
      해당 위치에 로봇이 여러 개 있다면 제거하는 방식으로 충돌을 처리합니다.
  • 문제점:
    • 문자열 생성, StringBuilder의 사용, HashMap의 키 생성 및 파싱 등
      고수준 자료구조를 사용하면서 불필요한 연산이 많이 발생합니다. ⏱️
    • 이로 인해 최적화가 덜 되어 실행 속도가 느려집니다.

2️⃣ 최적화 아이디어 (2차원 배열과 그리디 이동)

  • 개선 내용:
    • int[][] map 사용:
      전체 격자를 나타내는 2차원 배열을 사용하여,
      각 칸에 있는 로봇의 수를 직접 업데이트합니다.
      이는 메모리 접근이 연속적이어서 캐시 효율성이 좋고,
      불필요한 문자열 연산을 제거할 수 있습니다.
  • 로봇 이동 방식 최적화:
    • 로봇들은 나의 로봇에게 항상 가까워지기 때문에,
      9방향 전체를 탐색하는 대신,
      x좌표와 y좌표를 각각 비교하여 한 칸씩
      나의 로봇 쪽으로 이동시키는 그리디한 방식으로 처리합니다.
  • 충돌 처리:
    • 이동 후, 2차원 배열을 순회하면서
      각 칸에 로봇이 여러 개 존재하는 경우 해당 칸의 로봇들을 제거합니다.
  • 기대 효과:
    • 문자열 처리와 HashMap 연산에 따른 오버헤드가 제거되어,
      실행 속도가 크게 개선됩니다. 🚀

🔍 최종 코드 설명

원래 코드 vs. 최적화 아이디어 비교

  • 원래 코드:
    • 자료구조: Queue, HashMap, StringBuilder
    • 이동 처리: 각 로봇마다 9방향을 평가하고,
      문자열로 좌표를 생성해 HashMap에 저장한 뒤, 충돌 여부를 확인
    • 문제점:
      문자열 연산과 HashMap의 키 생성 및 파싱으로 인한 오버헤드 발생
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, M;

    private static int[] moveSeq;
    private static char[][] map;

    private static Queue<int[]> opponents = new ArrayDeque<>();
    private static int mx, my;
    private static int[][] dir = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 0}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};

    private static int answer = 0;

    public static void main(String[] args) throws IOException {
        setting();
        if (!isGamePossible()) System.out.println("kraj " + answer);
        else printMap();
    }

    private static void printMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    private static boolean isGamePossible() {
        for (int i = 0; i < moveSeq.length; i++) {
            answer++;
            if (!isMovePossible(moveSeq[i]) || !isOpponentsPossible()) {
                return false;
            }
        }
        return true;
    }

    private static boolean isOpponentsPossible() {
        Map<String, Integer> nextPosition = new HashMap<>();
        int size = opponents.size();
        for (int i = 0; i < size; i++) {
            int[] cur = opponents.poll();
            int ox = cur[0];
            int oy = cur[1];
            int nextDir = -1;
            int sum = Integer.MAX_VALUE;
            for (int j = 0; j < dir.length; j++) {
                int dx = ox + dir[j][0];
                int dy = oy + dir[j][1];
                if (dx < 0 || dx >= N || dy < 0 || dy >= M) continue;
                int distance = Math.abs(mx - dx) + Math.abs(my - dy);
//                System.out.println(mx + " " + my + " | " + dx + " " + dy + " | " + distance + " " + j);
                if (sum > distance) {
                    sum = distance;
                    nextDir = j;
                }
            }
//            System.out.println();
            int dx = ox + dir[nextDir][0];
            int dy = oy + dir[nextDir][1];
//            System.out.println(dx + " " + dy);
            map[ox][oy] = '.';
            if (dx == mx && dy == my) return false;
            sb.append(dx).append(",").append(dy);
            nextPosition.put(sb.toString(), nextPosition.getOrDefault(sb.toString(), 0) + 1);
            sb.setLength(0);
        }
//        System.out.println("size : " + nextPosition.keySet().size());
        for (String cur : nextPosition.keySet()) {
            if (nextPosition.get(cur) == 1) {
                String[] splits = cur.split(",");
                int x = Integer.parseInt(splits[0]);
                int y = Integer.parseInt(splits[1]);
//                System.out.println(x + " " + y);
                opponents.add(new int[]{x, y});
                map[x][y] = 'R';
            }
        }
//        printMap();
        return true;
    }

    private static boolean isMovePossible(int num) {
        int dx = mx + dir[num][0];
        int dy = my + dir[num][1];
        if (map[dx][dy] == 'R') return false;
        map[mx][my] = '.';
        map[dx][dy] = 'I';
        mx = dx;
        my = dy;
//        printMap();
        return true;
    }

    private static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];

        for (int i = 0; i < N; i++) {
            String mapInput = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = mapInput.charAt(j);
                if (map[i][j] == 'I') {
                    my = j;
                    mx = i;
                } else if (map[i][j] == 'R') opponents.add(new int[]{i, j});
            }
        }
        String moveInput = br.readLine();
        moveSeq = new int[moveInput.length()];
        for (int i = 0; i < moveSeq.length; i++) {
            moveSeq[i] = (moveInput.charAt(i) - '0') - 1;
        }
    }

}
  • 최적화 아이디어:
    • 자료구조: int[][] map (2차원 배열)
    • 이동 처리:
      • 각 로봇의 위치를 2차원 배열에 직접 기록
      • 나의 로봇과 상대 로봇의 x, y 좌표를 각각 비교하여
        그리디하게 한 칸씩 나의 로봇 방향으로 이동
    • 충돌 처리:
      • 전체 배열을 순회하여, 같은 칸에 여러 로봇이 있으면 모두 제거
    • 장점:
      • 불필요한 문자열 처리, HashMap 연산, Queue 관리 없이
        간결하게 격자 전체를 순회하며 업데이트하므로,
        훨씬 빠른 실행 속도를 기대할 수 있음.

📌 결론

  • 원래 구현:
    문자열 처리, HashMap, Queue 등을 사용하여 기능적으로는 문제를 해결했지만,
    과도한 연산 오버헤드로 인해 최적화가 부족함.
  • 최적화 아이디어:
    2차원 배열(int[][] map)을 사용하여 격자 내 로봇 위치를 직접 관리하고,
    각 로봇을 그리디하게 나의 로봇 방향으로 한 칸씩 이동시키며,
    이동 후 전체 배열을 순회하여 충돌을 처리하는 방식이
    불필요한 연산을 줄여 훨씬 빠른 속도를 달성할 수 있음.
profile
멋있는 사람 - 일단 하자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN