[백준 23031] 으어어… 에이쁠 주세요.. [Java]

문제

http://boj.ma/23031

요약

• 아리와 학생 좀비는 모두 아래 방향을 보고 있다.
• 아리는 가장 왼쪽 위에 위치한다.
• 아리는 벽에 부딪히게 되면 전진하지 못하고 제자리에 머문다.
• 아리는 스위치가 있는 칸에 도착하면 좀비랑 마주치기 전에 스위치를 켠다.
• 아리는 스위치가 켜져 불이 밝혀진 영역에서는 좀비를 만나도 기절하지 않는다.
• 아리는 스위치가 있는 칸에서는 좀비를 만나도 기절하지 않는다.
• 학생 좀비는 벽에 막혀 전진하지 못할 경우 반대 방향으로 회전한다.

---

풀이 과정

아이디어

우선 학생 좀비의 위치를 파악하자. 만약 학생 좀비가 하나도 없다면 아리는 기절하지 않는다.

private static boolean solve(char[] A) {
    // find Zombie
    List<User> zombies = new ArrayList<>();
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (board[i][j] == ZOMBIE) {
                zombies.add(new User(i, j));
            }
        }
    }
    if (zombies.isEmpty()) {
        return true;
    }

아리가 학생 좀비와 스위치가 있는 칸에 도달해도 스위치를 먼저 키면 기절하지 않는다는 조건이 있으므로, 아리가 학생 좀비보다 먼저 움직이도록 하자.

만약 이동한 위치가 스위치가 있는 공간이라면 불을 켜주자.

User user = new User(0, 0);
while (!actions.isEmpty()) {
    /*
    아리 먼저 움직인다.
     */
    switch (actions.poll()) {
        case 'F':
            int nx = user.x + dx[user.dir];
            int ny = user.y + dy[user.dir];
            if (isValid(nx, ny)) {
                user.x = nx;
                user.y = ny;
                if (board[nx][ny] == SWITCH) {
                    for (int i = -1; i <= 1; ++i) {
                        for (int j = -1; j <= 1; ++j) {
                            if (isValid(nx + i, ny + j)) {
                                light[nx + i][ny + j] = true;
                            }
                        }
                    }
                }
            }
            break;
        case 'L':
            user.dir = (user.dir + 1) % 4;
            break;
        case 'R':
            user.dir = (user.dir + 3) % 4;
            break;
    }

다음으로 학생 좀비들을 움직여주자.

아리가 먼저 움직였으므로 이미 학생 좀비와 같은 영역에 있거나, 학생 좀비가 이동할 다음 영역에 아리가 있을 수 있다.

    /*
    학생 좀비들이 움직인다.
     */
    for (User zombie : zombies) {
        if (faint(zombie.x, zombie.y, user)) return false;

        int nx = zombie.x + dx[zombie.dir];
        int ny = zombie.y + dy[zombie.dir];

        if (isValid(nx, ny)) {
            if (faint(nx, ny, user)) return false;
            zombie.x = nx;
            zombie.y = ny;
        } else {
            zombie.reverse();
        }
    }	
}

좀비와 아리가 같은 위치이고, 불이 안 켜진 영역인지 검사해서 기절 여부를 판별하자.

private static boolean faint(int x, int y, User user) {
    return x == user.x && y == user.y
        && !light[x][y];
}

성능 분석

• 제출결과: Accepted / 104ms / 14,148KB

---

회고

처음 구현에서는 스위치를 켜면 불이 켜지는 영역을 원본 배열에 ‘X’로 표시했다.

추가 자료구조 없이 불이 켜진 칸과 그렇지 않은 칸을 구분하기 위함이였다.

하지만 불이 켜질 영역에 스위치가 있는 경우를 처리하지 않아 ‘X’로 덮어쓰는 문제가 있었고 올바른 시뮬레이션을 할 수 없었다.

물론 스위치와 불이 켜진 경우를 고려해 조건 분기를 작성한다면 원본 배열 하나만으로 문제를 해결할 수 있지만 제약 사항이 많아진다.

따라서 별도의 배열(light)를 사용하는 방법을 선택했다.

서로 다른 개념의 상태를 하나의 구조에서 표현해 단순화 하려는 시도가 오히려 구현을 복잡하게 만들 수 있음을 깨달았다.

---

참고

문제

http://boj.ma/23031

23031번: 으어어… 에이쁠 주세요..

 

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/23031.java

problem-solving/baekjoon-online-judge/normal/23031.java at main · rogi-rogi/problem-solving