온풍기 안녕! ( 삼성 SW 역량테스트 기출 ) - 백준 BOJ 23289

요근래 다음달에 있을 삼성 SW 역량테스트 대비로 기출문제 몇개를 시간재고 푸는중이다

앞서 두어개 정도는 1시간 ~ 1시간 30분 정도 걸려서 풀리길래 할만하다고 생각했는데 세번째 문제로 끝판왕을 만났다

한 4시간정도 걸린 것 같다 😩

 

순수 구현으로 난이도가 플레티넘 5 이다.. 어쩐지 어렵더라

 

접을까 말까 고민하다가 결국에는 풀렸는데

그 과정에서 몇개 실수한 것 + 테크닉들을 정리해 다음에는 같은 실수를 반복하지 않으려고 한다

 

아래는 문제 링크이다

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

23289번: 온풍기 안녕!

 

지문이 너무 길어서 캡처는 생략...

 

---

실수들

입력값

1-indexed 로 입력값이 주어졌는데, 0-indexed 로 처리했다

입력값의 범위, range, type 늘 확인해야한다

 

복붙하고 세부사항 안고치기

set.add(getWallInfo(row, col, row - 1, col));
set.add(getWallInfo(row - 1, col, row - 1, col));	// 복붙해놓고 뒤에껄 안고쳤다

 

위처럼 비슷한 코드를 작성할 경우, 이전껄 복사해서 그 다음줄에 붙여넣는데

문제는 붙여넣고 나서 인자값이나 변수명 같이 살짝 수정이 필요한 부분에 있어서 자주 빼먹는다

타자치는 시간 10초 아끼려다가 30분을 날리게 된 케이스. 앞으로는 귀찮더라도 직접 작성하던가, 복붙을 꼼꼼하게 해야겠다

 

지문 제대로 읽기

사실 이건 내 실수기도 하지만 출제자 측에서 의도한 느낌이 없지않아 있다...

시뮬레이션 조건에서 2차원 grid에서 좌,우로 탐색 시 대각선 탐색은 행이동 후 열이동 이었는데

상,하 탐색도 당연히 행이동 후 열이동 인줄 알고 코드를 작성했다가 실제로는 열이동 후 행이동이어서 원인파악에 시간을 많이 허비했다.

좌,우 탐색에 대한 조건은 지문에서 명확하게 알려주었지만, 상,하 탐색의 경우 예시를 통해 넌지~시 알려주고 있어서 간과했었다

조금 긴 지문이어도 귀찮다고 날려읽지 말고 꼼꼼하게 읽어야 겠다

 

---

테크닉

한꺼번에 변화하는 2차원 grid 상의 데이터

 

2차원 grid 상에서 데이터를 조작하는 요구조건 이다

특이한 점이라면, n번 째 데이터의 조작이 n + 1 번째의 데이터의 조작에 영향을 미칠 때

탐색순서에 의해 데이터의 조작이 동기적으로 수행되는것이 아니라, 전체 데이터 조작이 한꺼번에 이루어져야 한다는 것이 조건이었다

 

이 문제를 조금 간단히 치환해보자

2차원 grid 를 순회하며, 각 칸에 인접한 모든 유효한 칸의 데이터들의 합을 현재 칸에 더하는 작업을 수행한다 해보자

 

1  2  3       7   11  11
4  5  6   =>  17  25  23 
7  8  9       19  29  23

 

위의 예시와 같이 왼쪽의 상태에서 오른쪽으로 데이터들이 조작되면 되는것인데, 만약 데이터들의 조작이 탐색순서에 따라 동기적으로 이루어진다면

 

public static void traverse(int[][] grid) {
    int rowSize = grid.length;
    int colSize = grid[0].length;

    for(int r = 0; r < rowSize; r++) {
        for(int c = 0; c < colSize; c++) {
            int[][] adjacentPositions = getAdjacentPositions(grid, r, c);

            int adjacentDataSum = Arrays.stream(adjacentPositions)
                    .map(pos -> grid[pos[0]][pos[1]])
                    .reduce(0, Integer::sum);

            grid[r][c] += adjacentDataSum;
        }
    }
}

public static int[] dr = new int[]{ -1, 0, 1, 0 };
public static int[] dc = new int[]{ 0, 1, 0, -1 };

public static int[][] getAdjacentPositions(int[][] grid, int row, int col) {
    return IntStream.range(0, 4)
            .mapToObj(index -> new int[]{ row + dr[index], col + dc[index] })
            .filter(pos -> isPosValid(grid, pos[0], pos[1]))
            .toArray(int[][]::new);
}

public static boolean isPosValid(int[][] grid, int row, int col) {
    int rowSize = grid.length;
    int colSize = grid[0].length;

    return row >= 0 && col >= 0 && row < rowSize && col < colSize;
}

/**
 결과

 7 17 26
 23 59 100
 38 114 223
*/

 

각 칸마다 인접한 칸의 데이터들의 합이 누적된 결과가 나오게 된다

데이터의 조작이 탐색순서에 상관없이 한꺼번에 이루어지기 위해서는 다음과 같이 각 칸의 인접한 값의 합을 캐싱해놓음으로서 해결할 수 있다

 

// travrse 메소드만 수정

public static void traverse(int[][] grid) {
    int rowSize = grid.length;
    int colSize = grid[0].length;

    // 인접 데이터들의 합을 캐싱해놓을 cache
    int[][] cache = new int[rowSize][colSize];

    for(int r = 0; r < rowSize; r++) {
        for(int c = 0; c < colSize; c++) {
            int[][] adjacentPositions = getAdjacentPositions(grid, r, c);

            int adjacentDataSum = Arrays.stream(adjacentPositions)
                    .map(pos -> grid[pos[0]][pos[1]])
                    .reduce(0, Integer::sum);

            cache[r][c] = adjacentDataSum;
        }
    }

    // cache 데이터를 grid 에 업데이트
    for(int r = 0; r < rowSize; r++) {
        for (int c = 0; c < colSize; c++) {
            grid[r][c] += cache[r][c];
        }
    }
}

 

이와 같이 간단한 방법으로 문제의 해결이 가능하다 v

 

 

좌표에 존재하지 않는 데이터 관리

 

2차원 grid 가 사용되는 대표적인 문제로는 미로찾기가 있다

파란색이 벽이다 ( 그림출처: https://digest1.tistory.com/7 )

 

위와 같이 벽으로 막힌 부분은 지나갈 수 없는 조건을 걸고 grid 를 탐색하게 되는데, 이는 탐색하고자 하는 위치의 data의 확인을 수행하는 간단한 코드로 시뮬레이션이 가능하다

 

// 1은 벽, 0은 지나갈 수 있는 공간

public static boolean isPosValid(int[][] grid, int row, int col) {
    int rowSize = grid.length;
    int colSize = grid[0].length;

    return row >= 0 && col >= 0 && row < rowSize && col < colSize && grid[row][col] != 1;
}

 

근데 이 문제에서는 정말 까다로운 조건을 내걸었다,

벽이 존재하지만, 이는 gird 상의 데이터로 표현되는것이 아니라 좌표간의 상태로 표현되었다

 

 

이 조건때문에 플레티넘 난이도로 책정되지 않았을까?

 

이제 gird 의 탐색에 있어서, 단순하게 현재 좌표를 기준으로 주변 칸들만의 방문가능여부를 확인하는 형태가 아니라 좌표간의 이동여부까지 확인하는 형식으로 문제가 발전되었다

 

참고로 나는 후술할 풀이대로 문제를 해결하지 않았다, 좌표간 이동에서 벽의 상태를 해시함수를 통해 관리했는데 이는 다양한 문제에 적용될 수 있는 방법이라 별도의 글로 작성하였다. 자세한 내용은 https://lomuto.tistory.com/8 을 참고하면 된다

 

문제 풀이가 끝난 후 다른 사람들의 풀이를 참고한 결과, 제일 괜찮았던 접근법은 3차원 grid 를 통한 문제의 해결이었다

 

// UP, DOWN, RIGHT, LEFT 순으로 북,남,동,서 를 표시
// 최종적으로는 ordinal 메소드를 통해 int 값을 사용할 것 이지만, 실수를 피하기 위해 사용
enum Direction {
    UP,
    DOWN,
    RIGHT,
    LEFT
}

// isMovable 메소드를 통해 이동여부 확인
// 각 좌표의 동서남북 이동가능 여부를 저장하는 3차원 int 배열 vectorStatus
// isMovable 메소드 호출 시 [srcRow, srcCol] 과 [destRow, destCol] 은 인접한 좌표임이 보장
// 1이 이동가능, 0은 불가능
public static boolean isMovable(int[][] grid, int[][][] vectorStatus, int srcRow, int srcCol, int destRow, int destCol){
	if(isPosValid(grid, destRow, destCol) == false){
    	return false;
    }
    
    // 북
	if(srcRow - 1 == destRow){
    	return vectorStatuc[srcRow][srcCol][Direction.UP.ordinal()] == 1;
    }
    
    // 남
	if(srcRow + 1 == destRow){
    	return vectorStatuc[srcRow][srcCol][Direction.DOWN.ordinal()] == 1;
    }
    
    // 동
	if(srcCol + 1 == destCol){
    	return vectorStatuc[srcRow][srcCol][Direction.RIGHT.ordinal()] == 1;
    }
    
    // 서
	if(srcCol - 1 == destCol){
    	return vectorStatuc[srcRow][srcCol][Direction.LEFT.ordinal()] == 1;
    }
}

public static boolean isPosValid(int[][] grid, int row, int col) {
    int rowSize = grid.length;
    int colSize = grid[0].length;

    return row >= 0 && col >= 0 && row < rowSize && col < colSize;
}

 

개인적으로 정말 괜찮은 방법이라 생각한다, 아마 나중에 비슷한 문제를 만나면 이렇게 해결하지 않을까 싶다

 

한가지 주의할 점 이라면, 입력값에서 좌표간의 벽 상태가 주어질 때 좌표기준으로 이는 bi-directional 해야하므로

좌표간 방문가능 여부를 양방향으로 업데이트 해주어야 한다

 

public static void updateVectorStatus(int[][][] vectorStatus, int srcRow, int srcCol, int destRow, int destCol) {
	// src 기준 북, dest 기준으로는 남
	if(srcRow - 1 == destRow){
    	vectorStatuc[srcRow][srcCol][Direction.UP.ordinal()] = 0;
        vectorStatuc[destRow][destCol][Direction.DOWN.ordinal()] = 0;
        return;
    }
    
    // src 기준 동, dest 기준으로는 서
	if(srcCol + 1 == destCol){
    	vectorStatuc[srcRow][srcCol][Direction.RIGHT.ordinal()] = 0;
        vectorStatuc[destRow][destCol][Direction.LEFT.ordinal()] = 0;
        return;
    }
    
    // 이하 남, 서 동일...
}

 

---

최종 코드

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

class Main {
    public static int mapRowSize;
    public static int mapColSize;
    public static int targetTemperature;
    public static List<Heater> heaterList = new ArrayList<>();
    public static List<int[]> observingPosList = new ArrayList<>();
    public static Set<Integer> wallSet = new HashSet<>();

    public static Integer getWallInfo(int r0, int c0, int r1, int c1) {
        // 최대가 19, 19
        return r0 + 20 * c0 + 1000 * r1 + 20000 * c1;
    }

    public static boolean isMovable(int srcRow, int srcCol, int destRow, int destCol) {
        if (isPosValid(destRow, destCol) == false) {
            return false;
        }

        return wallSet.contains(getWallInfo(srcRow, srcCol, destRow, destCol)) == false;
    }

    public static boolean isFlowable(int srcRow, int srcCol, int destRow, int destCol, Direction direction) {
        if (isPosValid(destRow, destCol) == false) {
            return false;
        }

        // isDiagonal direction
        if (Math.abs(destRow - srcRow) == 1 && Math.abs(destCol - srcCol) == 1) {
            if (direction == Direction.LEFT || direction == Direction.RIGHT)
                return wallSet.contains(getWallInfo(srcRow, srcCol, destRow, srcCol)) == false && wallSet.contains(getWallInfo(destRow, srcCol, destRow, destCol)) == false;

            // down or up
            return wallSet.contains(getWallInfo(srcRow, srcCol, srcRow, destCol)) == false && wallSet.contains(getWallInfo(srcRow, destCol, destRow, destCol)) == false;
        }

        return wallSet.contains(getWallInfo(srcRow, srcCol, destRow, destCol)) == false;
    }

    public static boolean isPosValid(int row, int col) {
        return row >= 0 && col >= 0 && row < mapRowSize && col < mapColSize;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] firstRowInputs = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        mapRowSize = firstRowInputs[0];
        mapColSize = firstRowInputs[1];
        targetTemperature = firstRowInputs[2];

        // first input
        for (int r = 0; r < mapRowSize; r++) {
            int[] column = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            for (int c = 0; c < mapColSize; c++) {
                int num = column[c];

                switch (num) {
                    case 0:
                        break;
                    case 1: {
                        heaterList.add(new Heater(r, c, Direction.RIGHT));
                        break;
                    }
                    case 2: {
                        heaterList.add(new Heater(r, c, Direction.LEFT));
                        break;
                    }
                    case 3: {
                        heaterList.add(new Heater(r, c, Direction.UP));
                        break;
                    }
                    case 4: {
                        heaterList.add(new Heater(r, c, Direction.DOWN));
                        break;
                    }
                    case 5: {
                        observingPosList.add(new int[]{r, c});
                        break;
                    }
                    default:
                        throw new RuntimeException(String.format("Unexpected input %d", num));
                }
            }
        }

        int n = Integer.parseInt(reader.readLine());
        for (int i = 0; i < n; i++) {
            int[] input = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            int row = input[0] - 1;
            int col = input[1] - 1;
            int t = input[2];

            if (t == 0) {
                wallSet.add(getWallInfo(row, col, row - 1, col));
                wallSet.add(getWallInfo(row - 1, col, row, col));
            } else {
                wallSet.add(getWallInfo(row, col, row, col + 1));
                wallSet.add(getWallInfo(row, col + 1, row, col));
            }
        }

        int chocolateCount = 0;

        int[][] map = new int[mapRowSize][mapColSize];

        while (chocolateCount < 101) {

            heaterList.forEach(heater -> heater.propagateHeat(map));

            flowTemperature(map);
            decreaseEdgeTemperature(map);

            chocolateCount++;

            int count = 0;
            for (int[] observingPos : observingPosList) {
                int row = observingPos[0];
                int col = observingPos[1];

                if (map[row][col] >= targetTemperature) {
                    count++;
                }
            }

            if (count == observingPosList.size()) {
                break;
            }
        }

        System.out.println(chocolateCount);
    }

    private static int[] dr = new int[]{-1, 0, 1, 0};
    private static int[] dc = new int[]{0, 1, 0, -1};

    private static void flowTemperature(int[][] map) {
        int[][] temperatureToAdd = new int[mapRowSize][mapColSize];

        for (int r = 0; r < mapRowSize; r++) {
            for (int c = 0; c < mapColSize; c++) {

                for (int i = 0; i < 4; i++) {
                    int nextRow = r + dr[i];
                    int nextCol = c + dc[i];

                    if (isMovable(r, c, nextRow, nextCol) == false || map[nextRow][nextCol] > map[r][c]) {
                        continue;
                    }

                    // 현재위치의 온도 > 관찰중인 좌표 온도  가 보장
                    int adjustment = (map[r][c] - map[nextRow][nextCol]) / 4;
                    temperatureToAdd[nextRow][nextCol] += adjustment;
                    temperatureToAdd[r][c] -= adjustment;
                }

            }
        }

        // apply changes
        for (int r = 0; r < mapRowSize; r++) {
            for (int c = 0; c < mapColSize; c++) {
                map[r][c] += temperatureToAdd[r][c];
            }
        }
    }

    private static void decreaseEdgeTemperature(int[][] map) {
        for (int r = 0; r < mapRowSize; r++) {
            for (int c = 0; c < mapColSize; c++) {
                if ((r == 0 || r == mapRowSize - 1) || (c == 0 || c == mapColSize - 1)) {
                    map[r][c] = Math.max(0, map[r][c] - 1);
                }
            }
        }
    }
}

class Heater {
    int row;
    int col;
    Direction direction;

    public static int[][] getNextPos(int row, int col, Direction direction) {
        switch (direction) {
            case UP:
                return new int[][]{new int[]{row - 1, col}, new int[]{row - 1, col - 1}, new int[]{row - 1, col + 1}};
            case DOWN:
                return new int[][]{new int[]{row + 1, col}, new int[]{row + 1, col - 1}, new int[]{row + 1, col + 1}};
            case RIGHT:
                return new int[][]{new int[]{row, col + 1}, new int[]{row + 1, col + 1}, new int[]{row - 1, col + 1}};
            case LEFT:
                return new int[][]{new int[]{row, col - 1}, new int[]{row + 1, col - 1}, new int[]{row - 1, col - 1}};
            default:
                throw new RuntimeException(String.format("Unexpected direction %s", direction));
        }
    }

    public Heater(int row, int col, Direction direction) {
        this.row = row;
        this.col = col;
        this.direction = direction;
    }

    public void propagateHeat(int[][] map) {
        boolean[][] isVisited = new boolean[Main.mapRowSize][Main.mapColSize];
        int[] pos = getFirstPos();

        int row = pos[0];
        int col = pos[1];

        isVisited[row][col] = true;

        heatDfs(map, isVisited, row, col, 5);
    }

    private void heatDfs(int[][] map, boolean[][] isVisited, int row, int col, int heat) {
        if (heat == 0) {
            return;
        }

        map[row][col] += heat;

        for (int[] nextPos : getNextPos(row, col, this.direction)) {
            int nextRow = nextPos[0];
            int nextCol = nextPos[1];

            if (Main.isFlowable(row, col, nextRow, nextCol, direction) == false || isVisited[nextRow][nextCol]) {
                continue;
            }

            isVisited[nextRow][nextCol] = true;
            heatDfs(map, isVisited, nextRow, nextCol, heat - 1);
        }
    }

    private int[] getFirstPos() {
        switch (direction) {
            case UP:
                return new int[]{row - 1, col};
            case DOWN:
                return new int[]{row + 1, col};
            case LEFT:
                return new int[]{row, col - 1};
            case RIGHT:
                return new int[]{row, col + 1};
            default:
                throw new RuntimeException(String.format("Unexpected direction %s", direction));
        }
    }
}

enum Direction {
    UP,
    RIGHT,
    LEFT,
    DOWN
}