147. [삼성기출43]Python 백준 23289 온풍기 안녕! + 디버깅 과정

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 232889 온풍기 안녕! 입니다.

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

23289번: 온풍기 안녕!

 

2일동안 도전한 문제다.

2시간 정도만에 코드를 작성했지만 처음에는 테스트 케이스 2개를 통과하지 못했었다.

내가 작성한 코드의 알고리즘이 잘못됐나 살펴보았지만 도저히 버그를 찾지 못했었다.

이때 알고리즘이 잘못되지 않았다고 생각이 들면 세부적으로 코드를 살펴봐 잘못 작성한 부분이 있나 살펴봐야 한다.

처음부터 코드를 읽어 내려갔고, 바람이 이동할 때 경로에 벽이 있다면 q에 바람을 넣지 않아야 된다.

이때 아래로 바람이 이동할 때 경로상의 벽의 위치를 찾는 코드에 오타가 있는걸 발견하고 수정했다.

# 우, 좌, 상, 하
check_wall = (0,
              (((0, 0, 0), (-1, 0, 1)), ((0, 0, 1),), ((1, 0, 0), (1, 0, 1))),
              (((1, 0, 0), (1, -1, 1)), ((0, -1, 1),), ((0, 0, 0), (-1, -1, 1))),
              (((0, -1, 1), (0, -1, 0)), ((0, 0, 0),), ((0, 0, 1), (0, 1, 0))),
              (((0, 0, 1), (1, 1, 0)), ((1, 0, 0),), ((0, -1, 1), (1, -1, 0))),
              )

이후 제출을 했는데 또 실패가 떠서 테스트케이스 입력을 살펴보니

온풍기 방향 2번, 1번이 테스트케이스가 없어 그 곳에 문제가 있을것이라고 짐작하고 코드를 다시 살펴보니

온풍기 방향 2번에 문제가 있었다. 수정 이후 성공!

 

논리에 문제가 있을것이라고 생각이 들어 해당방향으로 생각하다보니 디버깅이 오래걸렸다.

논리에 문제가 없다면, 예외에 문제가 있는지 생각하고, 예외에 문제가 없다면 오타가 없는지 살펴보는 습관을 길러야겠다.

 

문제 접근

사실 이번 문제는 구현을 꼼꼼하게 틀리지 않고 해야된다는 점이 어렵지 알고리즘 자체는 어렵지 않았다.

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
2. 온도가 조절됨
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
4. 초콜릿을 하나 먹는다.
5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

위의 순서대로 반복하면 된다.

먼저 아래와 같이 top_down으로 코드를 구현했다. 아래처럼 모듈 형식으로 구현해야 디버깅이 편하다.

def solve():
    cnt = 0
    while True:
        heat() #1
        adjust_temp() #2
        cool_border() #3
        cnt += 1 #4
        if cnt > 100:
            return cnt
        if check_temperature(): #5
            break
    return cnt

print(solve())

 

여기서 heat() 가 핵심인데  바람이 이동하는 것 까지 구현하는 것은 어렵지 않으나 경로상에 벽이 있는지 확인하는 코드가 구현하기 어렵다.

필자는 heat()를 다음과 같이 구현했다.

1. warm_air의 좌표는 온풍기의 좌표가 아닌 바람이 처음 나온 곳의 좌표를 담았다.

2. 큐 안의 모든 좌표에 대해 바람 이동 방향으로 3개 좌표를 살펴보면 된다.

3. 이미 방문한 좌표는 다시 방문하지 않는다. (큐에 추가하지 않는다.)

4. 바람 이동 경로에 벽이 있다면 다시 방문하지 않는다. (큐에 추가하지 않는다.)

5. 큐에 다음 좌표를 추가 할 떄마다 온도를 1 도씩 낮췄다.

 

ndxy를 통해 바람 이동 방향의 새로운 좌표 3개를 탐색한다.

만약 방문하지 않았다면, check_wall을 통해 이동 경로에 벽이 있는지 확인한다.

안약 없다면 방문처리를 한 후 q에 새로운 좌표를 추가한다.

def heat():
    for x, y, d in warm_airs:
        visited = [[False for _ in range(C)] for _ in range(R)]
        q = deque()
        q.append((x, y, 5),)

        while q:
            x, y, temp = q.popleft()
            board[x][y] += temp
            if temp > 1:
                for index, (ndx, ndy) in enumerate(ndxy[d]):
                    nx, ny = x + ndx, y + ndy
                    if 0 <= nx < R and 0 <= ny < C:
                        if not visited[nx][ny]:
                            add_q = True
                            for w_x, w_y, t in check_wall[d][index]:
                                if (x + w_x, y + w_y, t) in walls:
                                    add_q = False
                            if add_q:
                                visited[nx][ny] = True
                                q.append((nx, ny, temp - 1))

 

 

Python 정답 코드

백준 23289 파이썬 코드입니다.

from collections import deque
R, C, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(R)]
check_list = []
warm_airs = []
walls = []
W = int(input())

ndxy = (0, ((-1, 1), (0, 1), (1, 1),), ((1, -1), (0, -1), (-1, -1),), ((-1, -1), (-1, 0), (-1, 1),), ((1, 1), (1, 0), (1, -1),),)

# 우, 좌, 상, 하
check_wall = (0,
              (((0, 0, 0), (-1, 0, 1)), ((0, 0, 1),), ((1, 0, 0), (1, 0, 1))),
              (((1, 0, 0), (1, -1, 1)), ((0, -1, 1),), ((0, 0, 0), (-1, -1, 1))),
              (((0, -1, 1), (0, -1, 0)), ((0, 0, 0),), ((0, 0, 1), (0, 1, 0))),
              (((0, 0, 1), (1, 1, 0)), ((1, 0, 0),), ((0, -1, 1), (1, -1, 0))),
              )

dx = [0, 0, 0, -1, 1]
dy = [0, 1, -1, 0, 0]

for w in range(W):
    x, y, t = list(map(int, input().split()))
    walls.append((x-1, y-1, t))

for i in range(R):
    for j in range(C):
        if board[i][j] != 0:
            if board[i][j] == 5:
                check_list.append((i, j))
            else:
                ni, nj = i + dx[board[i][j]], j + dy[board[i][j]]
                warm_airs.append([ni, nj, board[i][j]])
            board[i][j] = 0

def debug(board):
    for i in range(R):
        for j in range(C):
            print(board[i][j], end=" ")
        print()
    print()

def heat():
    for x, y, d in warm_airs:
        visited = [[False for _ in range(C)] for _ in range(R)]
        q = deque()
        q.append((x, y, 5),)

        while q:
            x, y, temp = q.popleft()
            board[x][y] += temp
            if temp > 1:
                for index, (ndx, ndy) in enumerate(ndxy[d]):
                    nx, ny = x + ndx, y + ndy
                    if 0 <= nx < R and 0 <= ny < C:
                        if not visited[nx][ny]:
                            add_q = True
                            for w_x, w_y, t in check_wall[d][index]:
                                if (x + w_x, y + w_y, t) in walls:
                                    add_q = False
                            if add_q:
                                visited[nx][ny] = True
                                q.append((nx, ny, temp - 1))

def adjust_temp():
    global board
    new_board = [[0 for _ in range(C)] for _ in range(R)]
    wall_coord = [0, (0, 0, 1), (0, -1, 1), (0, 0, 0), (1, 0, 0)]
    for i in range(R):
        for j in range(C):
            added = 0
            for d in range(1, 5):
                nx, ny = dx[d] + i, dy[d] + j
                if 0 <= nx < R and 0 <= ny < C:
                    if board[i][j] > board[nx][ny]:
                        wx, wy, t = wall_coord[d]
                        if (wx + i, wy + j, t) not in walls:
                            new_board[nx][ny] += (board[i][j] - board[nx][ny]) // 4
                            added += (board[i][j] - board[nx][ny]) // 4
            new_board[i][j] += (board[i][j] - added)
    board = new_board

def cool_border():
    for y in range(1, C - 1):
        if board[0][y] > 0:
            board[0][y] -= 1
        if board[R - 1][y] > 0:
            board[R - 1][y] -= 1
    for x in range(1, R - 1):
        if board[x][0] > 0:
            board[x][0] -= 1
        if board[x][C - 1] > 0:
            board[x][C - 1] -= 1

    for x, y in ((0, 0), (0, C - 1), (R - 1, 0), (R - 1, C - 1)):
        if board[x][y] > 0:
            board[x][y] -= 1

def check_temperature():
    for x, y in check_list:
        if board[x][y] < K:
            return False
    return True

def solve():
    cnt = 0
    while True:
        heat()
        adjust_temp()
        cool_border()
        cnt += 1
        if cnt > 100:
            return cnt
        if check_temperature():
            break
    return cnt

print(solve())

 

백준 23289 Python 코드였습니다.

감사합니다.