[PS] 백준20165 : 인내의 도미노 장인 호석(Java)

문제

https://www.acmicpc.net/problem/20165

20165번: 인내의 도미노 장인 호석

---

풀이

역시 구현+시뮬레이션 답게 장황한 문제의 지문에 조금 당황했지만..

이해하고 나면 막상 수월하게 풀이가 가능했던 문제

해당 문제에서 핵심 로직 : 공격에 관한 상태배열 관리

1. 입력의 방향은 Switch~case문으로 처리.
2. 시작 좌표 큐에 추가.
3. while문을 수행하면서 큐에서 꺼낸 좌표에 대해 로직 수행.
4. 큐에서 꺼낸 좌표의 상태값이 0이라면(넘어져있는 경우) continue
5. 넘어져있지 않다면 해당좌표 값 0으로 변경 및 해당 도미노의 길이만큼 넘어져있지 않은 도미노에 대해 큐에 추가.
6. 큐가 빌 때까지 3~5 로직 반복 수행.

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//BOJ_20165 인내의 도미노 장인 호석
public class Main {
    static int N, M, R, res;
    static int[][] map, copy;
    static int[] dx = new int[]{0,0,1,-1};
    static int[] dy = new int[]{1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken()); //라운드 횟수

        map = new int[N][M];
        copy = new int[N][M];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                copy[i][j] = map[i][j];
            }
        }

        for(int i=0; i<R; i++) {
            st = new StringTokenizer(br.readLine()); //공격
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            char d = st.nextToken().charAt(0); //방향

            Attack(x,y,d); //공격 로직

            st = new StringTokenizer(br.readLine()); //수비
            x = Integer.parseInt(st.nextToken())-1;
            y = Integer.parseInt(st.nextToken())-1;
            map[x][y] = copy[x][y];
        }

        //넘어지면 F
        //그 외는 S
        //매 라운드마다 공격 때 넘어진 도미노회수 출력
        sb.append(res).append("\\n"); //공격 턴에 넘어뜨린 도미노의 총 개수
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j] == 0) sb.append("F ");
                else sb.append("S ");
            }
            sb.append("\\n");
        }

        System.out.println(sb);

    }

    private static void Attack(int x, int y, char d) {
        //E:동, W:서, S:남, N:북
        switch (d) {
            case 'E':
                domino(x,y,0);
                break;
            case 'W':
                domino(x,y,1);
                break;
            case 'S':
                domino(x,y,2);
                break;
            case 'N':
                domino(x,y,3);
                break;
        }
    }

    private static void domino(int x, int y, int d) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x,y,map[x][y]});

        while(!q.isEmpty()) {
            int[] idx = q.poll();

            if(map[idx[0]][idx[1]] == 0) continue; //현재 상태값을 기준으로!..

            map[idx[0]][idx[1]] = 0; //현재좌표 넘어뜨리고 이후 연쇄 작용 큐에 추가
            res++; //결과값 증가

            int nx = idx[0];
            int ny = idx[1];
            for(int i=1; i<idx[2]; i++) {
                nx += dx[d];
                ny += dy[d];
                if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
                if(map[nx][ny] != 0) { //넘어지지 않은 도미노의 경우에만
                    q.offer(new int[]{nx,ny,map[nx][ny]});
                }
            }
        }
    }
}

---

정리

• 큐에서 꺼낸 좌표에 대해 0이 아닌지 판단하는 구문에서 map 상태배열을 참조하지 않고 큐의 값인 idx[2]를 참조하는 바람에 3/11 채점을 받고 당황하여 반례를 찾아 한동안 헤맴…
  • idx[2]를 참조해버리면 이미 0이 되어버린 좌표에 대해서도 res값을 증가하기 때문에 잘못된 값이 도출됨!..
• 이 후 반례를 찾았지만 없어서 직접 반례를 만들어보며 트라이해보는 과정에서 분명 공격자의 점수가 11이 나와야 하는데 15가 나오는 반례를 찾아서 겨우 풀이했다!…
  • 반례 만드는 건 항상 너무 어려운 듯… 하지만 직접 만들어보고 해결해보니 너무 좋은 경험이였다.

---

반례

입력
5 5 3
1 1 1 1 1
1 2 2 1 1
3 1 2 2 2
1 3 2 1 1
1 3 3 1 1
1 1 E
3 5
5 3 N
3 3
5 2 N
3 1

--------------------------------------
Flase Case
15
F F F S S 
S F F S S 
S F S S S 
S F F S S 
S F F S S
--------------------------------------
True Case
11
F F F S S 
S F F S S 
S F S S S 
S F F S S 
S F F S S