🔗 문제 링크
📝 문제 설명
이 문제는 R×C 크기의 격자 위에서 진행됩니다.
격자에는 나의 로봇("I")과 상대 로봇들("R")이 배치되어 있으며,
주어진 이동 명령에 따라 나의 로봇이 이동할 때마다 상대 로봇들은
나의 로봇을 향해 그리디하게 한 칸씩 이동합니다. 🤖➡️
특히, 상대 로봇이 같은 칸에 여러 개 모이면 모두 제거되고,
만약 나의 로봇이 상대 로봇과 같은 칸으로 이동하면 게임 오버가 됩니다. ❌
문제의 목표는 이동 명령을 모두 수행한 후의 최종 격자 상태를 출력하거나,
중간에 나의 로봇이 잡혔을 경우 "kraj <순서>"를 출력하는 것입니다.
✅ 접근 방식 및 시도한 방법들
1️⃣ 원래 구현 (문자열 처리, HashMap, Queue 사용)
- 구현 내용:
- Queue를 사용하여 상대 로봇(arduino)의 위치를 관리합니다.
- 각 이동마다 모든 상대 로봇에 대해 9방향(현재 위치 포함)으로 이동할 후보를 평가하고,
나의 로봇과의 거리를 기준으로 최적의 방향을 선택합니다.
- 충돌 처리:
- 이동 후, 각 로봇의 위치를 문자열로 표현하여 HashMap에 기록한 뒤,
해당 위치에 로봇이 여러 개 있다면 제거하는 방식으로 충돌을 처리합니다.
- 이동 후, 각 로봇의 위치를 문자열로 표현하여 HashMap에 기록한 뒤,
- 문제점:
- 문자열 생성,
StringBuilder의 사용,HashMap의 키 생성 및 파싱 등
고수준 자료구조를 사용하면서 불필요한 연산이 많이 발생합니다. ⏱️ - 이로 인해 최적화가 덜 되어 실행 속도가 느려집니다.
- 문자열 생성,
2️⃣ 최적화 아이디어 (2차원 배열과 그리디 이동)
- 개선 내용:
- int[][] map 사용:
전체 격자를 나타내는 2차원 배열을 사용하여,
각 칸에 있는 로봇의 수를 직접 업데이트합니다.
이는 메모리 접근이 연속적이어서 캐시 효율성이 좋고,
불필요한 문자열 연산을 제거할 수 있습니다.
- int[][] map 사용:
- 로봇 이동 방식 최적화:
- 로봇들은 나의 로봇에게 항상 가까워지기 때문에,
9방향 전체를 탐색하는 대신,
x좌표와 y좌표를 각각 비교하여 한 칸씩
나의 로봇 쪽으로 이동시키는 그리디한 방식으로 처리합니다.
- 로봇들은 나의 로봇에게 항상 가까워지기 때문에,
- 충돌 처리:
- 이동 후, 2차원 배열을 순회하면서
각 칸에 로봇이 여러 개 존재하는 경우 해당 칸의 로봇들을 제거합니다.
- 이동 후, 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 관리 없이
📌 결론
- 원래 구현:
문자열 처리,HashMap,Queue등을 사용하여 기능적으로는 문제를 해결했지만,
과도한 연산 오버헤드로 인해 최적화가 부족함. - 최적화 아이디어:
2차원 배열(int[][] map)을 사용하여 격자 내 로봇 위치를 직접 관리하고,
각 로봇을 그리디하게 나의 로봇 방향으로 한 칸씩 이동시키며,
이동 후 전체 배열을 순회하여 충돌을 처리하는 방식이
불필요한 연산을 줄여 훨씬 빠른 속도를 달성할 수 있음.
멋있는 사람 - 일단 하자