[221011] 백준 23289 : 온풍기 안녕!

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

23289번: 온풍기 안녕!

해당 문제는 구현해야 할 내용도 많아 상당히 까다로운 문제라고 할 수 있다. 시간 압박 속에서 풀게 되면 구현하는데 집중하는 나머지 사소한 것에 실수할 가능성이 매우 큰 문제였다. 평소에 시간을 재고 푸는데, 그러다 보니 마음이 급해져서 사소한 것들을 많이 놓치게 되었다. 결국 수 번의 틀렸습니다를 겪고 나서 시간을 재지 않고 차분한 마음으로 다시를 문제를 보고 나서야 놓쳤던 부분들이 눈에 들어오게 되었다.

 

결론 : 문제를 차분하게 읽고 풀어나가는 것이 빠른 문제풀이의 지름길이다.

 

1. 벽 관리를 어떻게 할 것인가?

 벽을 체크하는 것을 제외하면, 온도조절이나 바람이 나가는 경우에 대해서 푸는 것은 익숙한 부분(함정)이다. 본 포스팅에서는 벽을 체크하는 방법에 대해 최대한 설명하고자 한다.

 처음에 구상했던 내용은 가로 벽과 세로 벽을 두 부분으로 나누어서 3차원 배열로 정의했었다. 하지만, 이렇게 하면 의도하지 않은 곳에 벽이 세워지는 문제가 발생한다. 가령, 리스트의 0번이 가로 벽을 표현하고, 1번 인덱스가 세로 벽이라고 했을 때, 다음과 같이 구성하면 3행 6열과 4행 6열에 없던 가로 벽이 생기게 된다. 반례 폭격 맞기 쉬움.

 따라서 내가 있는 위치에서 동(오른쪽), 서(왼쪽), 남(아래쪽), 북(위쪽)을 확인했을 때 벽이 있도록 개별 정의를 해주면 벽 판단하기 수월해진다. 다음 그림에서 인덱스는 오, 왼, 위, 아래 순이다.

 이렇게 했을 때, (2, 5)에서 (3, 6)으로 바람이 퍼져나갈 때 벽 여부를 확인한다고 할 때, 현재 있는 위치 (2,5)에서 오른쪽([1, 0, 0, 0])에 벽이 있기 때문에 바람이 퍼져나갈 수 없다. 마찬가지로, (4, 5)에서 (5, 6)으로 바람이 퍼져나간다고 했을 때, (4, 5)의 오른쪽에는 벽이 없고, (5, 6) 기준으로는 위쪽([0, 0, 1, 0])에 벽이 있다고 정보가 표시가 되어 있기 때문에 바람이 퍼져나갈 수 없다. 이에 대한 소스코드 예는 다음과 같다.

def wall_check(x, y, nx, ny, main_d, stats):
    if stats == 0 : # 직진만 하면 됨
        if w_info[main_d][x][y] == 1 :
            return False
    else :
        if stats == 1 : # 각 방향에서 왼쪽으로 갔다가 메인 방향으로 감
            if main_d == 1 :
                if w_info[3][x][y] == 1 or w_info[2][nx][ny] == 1 :
                    return False
            elif main_d == 2 :
                if w_info[4][x][y] == 1 or w_info[1][nx][ny] == 1 :
                    return False
            elif main_d == 3 :
                if w_info[2][x][y] == 1 or w_info[4][nx][ny] == 1 :
                    return False
            else :
                if w_info[1][x][y] == 1 or w_info[3][nx][ny] == 1 :
                    return False
        elif stats == 2 : # 각 방향에서 오른쪽으로 갔다가 메인 방향으로 감
            if main_d == 1 :
                if w_info[4][x][y] == 1 or w_info[2][nx][ny] == 1 :
                    return False
            elif main_d == 2 :
                if w_info[3][x][y] == 1 or w_info[1][nx][ny] == 1 :
                    return False
            elif main_d == 3 :
                if w_info[1][x][y] == 1 or w_info[4][nx][ny] == 1 :
                    return False
            else :
                if w_info[2][x][y] == 1 or w_info[3][nx][ny] == 1 :
                    return False
    return True

2. 놓치기 쉬운 로직

 벽 판단 여부 짜느라 놓치기 쉬운 로직이 있다. 온풍기 작동할 때 BFS로 코드를 짜는 경우인데, 바람이 퍼져나갈 때 온도가 0도 이하가 되면 계산을 무시하도록 해줘야 한다. 예제에서는 7X8 배열이라 음수가 나오는 경우가 없는데, 배열이 20X20까지 정의할 수 있으므로 꼭 체크해줘야 한다. 이거 디버깅하는데 2일이 걸렸다. 예제와 백준 질문의 반례인 경우에 다 맞게 나오는 경우여서, 스스로 에지 케이스를 만들어서 해결할 수 있어야 한다.

if heat == 0 : continue

이에 대한 소스코드는 다음과 같다.

def operation():
    # 온풍기 방향 -> 1 : 오른쪽, 2 : 왼쪽, 3 : 위쪽, 4 : 아래쪽
    dx = [[], [0, -1, 1], [0, 1, -1], [-1, -1, -1], [1, 1, 1]]
    dy = [[], [1, 1, 1], [-1, -1, -1], [0, -1, 1], [0, 1, -1]]
    for x, y, d in h_info :
        x += dx[d][0]
        y += dy[d][0]
        heat_size = 5
        new_board[x][y] += heat_size
        q = [[x, y, d, heat_size-1]]
        visited = [[False for _ in range(C)] for _ in range(R)]
        visited[x][y] = True
        while q :
            x, y, d, heat = q[0]
            del q[0]
            if heat == 0 : continue
            for direction in range(3):
                nx = x + dx[d][direction]
                ny = y + dy[d][direction]
                if 0 <= nx < R and 0 <= ny < C :
                    check = wall_check(x, y, nx, ny, d, direction)
                    if not check :
                        continue
                    if check and not visited[nx][ny] :
                        q.append([nx, ny, d, heat - 1])
                        visited[nx][ny] = True
                        new_board[nx][ny] += heat

3. 전체 코드

메모리 : 119256 KB, 시간 : 380 ms, 풀이 시간 : inf

R, C, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(R)]
new_board = [[0 for _ in range(C)] for _ in range(R)]
W = int(input())
w_info = [[[0 for _ in range(C)] for _ in range(R)] for _ in range(5)]
h_info = []
c_info = []
for _ in range(W):
    x, y, t = map(int, input().split())
    x -= 1
    y -= 1
    if t == 0 :
        w_info[4][x-1][y] = 1
        w_info[3][x][y] = 1
    else :
        w_info[2][x][y+1] = 1
        w_info[1][x][y] = 1

for i in range(R):
    for j in range(C):
        if board[i][j] == 5 :
            c_info.append([i, j])
        elif 1 <= board[i][j] <= 4 :
            h_info.append([i, j, board[i][j]])

def wall_check(x, y, nx, ny, main_d, stats):
    if stats == 0 : # 직진만 하면 됨
        if w_info[main_d][x][y] == 1 :
            return False
    else :
        if stats == 1 : # 각 방향에서 왼쪽으로 갔다가 메인 방향으로 감
            if main_d == 1 :
                if w_info[3][x][y] == 1 or w_info[2][nx][ny] == 1 :
                    return False
            elif main_d == 2 :
                if w_info[4][x][y] == 1 or w_info[1][nx][ny] == 1 :
                    return False
            elif main_d == 3 :
                if w_info[2][x][y] == 1 or w_info[4][nx][ny] == 1 :
                    return False
            else :
                if w_info[1][x][y] == 1 or w_info[3][nx][ny] == 1 :
                    return False
        elif stats == 2 : # 각 방향에서 오른쪽으로 갔다가 메인 방향으로 감
            if main_d == 1 :
                if w_info[4][x][y] == 1 or w_info[2][nx][ny] == 1 :
                    return False
            elif main_d == 2 :
                if w_info[3][x][y] == 1 or w_info[1][nx][ny] == 1 :
                    return False
            elif main_d == 3 :
                if w_info[1][x][y] == 1 or w_info[4][nx][ny] == 1 :
                    return False
            else :
                if w_info[2][x][y] == 1 or w_info[3][nx][ny] == 1 :
                    return False
    return True

def operation():
    # 온풍기 방향 -> 1 : 오른쪽, 2 : 왼쪽, 3 : 위쪽, 4 : 아래쪽
    dx = [[], [0, -1, 1], [0, 1, -1], [-1, -1, -1], [1, 1, 1]]
    dy = [[], [1, 1, 1], [-1, -1, -1], [0, -1, 1], [0, 1, -1]]
    for x, y, d in h_info :
        x += dx[d][0]
        y += dy[d][0]
        heat_size = 5
        new_board[x][y] += heat_size
        q = [[x, y, d, heat_size-1]]
        visited = [[False for _ in range(C)] for _ in range(R)]
        visited[x][y] = True
        while q :
            x, y, d, heat = q[0]
            del q[0]
            if heat == 0 : continue
            for direction in range(3):
                nx = x + dx[d][direction]
                ny = y + dy[d][direction]
                if 0 <= nx < R and 0 <= ny < C :
                    check = wall_check(x, y, nx, ny, d, direction)
                    if not check :
                        continue
                    if check and not visited[nx][ny] :
                        q.append([nx, ny, d, heat - 1])
                        visited[nx][ny] = True
                        new_board[nx][ny] += heat

def resize_temp():
    temp_info = []
    # 우, 좌, 상, 하
    dx = [0, 0, 0, -1, 1]
    dy = [0, 1, -1, 0, 0]
    for i in range(R):
        for j in range(C):
            if new_board[i][j] == 0 : continue
            x, y, temper = i, j, new_board[i][j]
            for d in range(1, 5):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0 <= nx < R and 0 <= ny < C :
                    check = wall_check(x, y, nx, ny, d, 0)
                    if not check : continue
                    if check :
                        T1 = temper
                        T2 = new_board[nx][ny]
                        if T1 > T2 :
                            diff = (T1 - T2)//4
                            temp_info.append([nx, ny, diff])
                            temp_info.append([x, y, -diff])
    for x, y, diff in temp_info:
        new_board[x][y] = max(new_board[x][y] + diff, 0)

def cooling():
    for i in range(R):
        if i == 0 or i == R - 1:
            for j in range(C):
                if new_board[i][j] > 0 :
                    new_board[i][j] -= 1
        else :
            if new_board[i][0] > 0 :
                new_board[i][0] -= 1
            if new_board[i][-1] > 0 :
                new_board[i][-1] -= 1

def solve():
    chocolate = 0
    while True :
        operation()
        resize_temp()
        cooling()
        chocolate += 1
        cnt = 0
        for x, y in c_info :
            if new_board[x][y] >= K :
                cnt += 1
        if cnt == len(c_info) : break
        if chocolate > 100 :
            chocolate = 101
            break
    print(chocolate)
solve()