[BOJ] 20165. 인내의 도미노 장인 호석(Python) / Simulation

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

# 문제 이해 못 하고 1시간 30분동안 시간 날리고, 문제 이해하고 다 지우고 새로 다시 풀어서 28분만에 pass

• 사용 알고리즘 : Simulation + Recursive Function
• 공격, 수비 전에 미리 해둔 것
  • 공격 시작 좌표, 수비 시작 좌표 Input 받으면서 다루기 좋게 indexing 해준다.
  • 수비할 때, 원래 맵에 있는 도미노 정보로 복원해줘야 하기 때문에 raw배열에 board맵을 복사해놓는다.
  • 동서남북 E, W, S, N에 대해 이동하는 델타 좌표 dirInfo에 딕셔너리로 미리 저장해둔다.
• 공격 함수 domino()는 (시작 위치, 방향, 길이) 인자로 넘기면 재귀로 도미노를 넘긴다.
  • 값이 있을 때만 0으로 바꿔주면서 매 라운드별로 넘기는 도미노 갯수 temp를 갱신해준다.
  • 맵의 해당 위치에 저장된 길이-1만큼 이동하며 재귀로 정보를 넘긴다.
• 수비는 미리 저장해둔 raw 배열에서 해당 위치 정보를 가져와 board에 복원한다.
• 출력 형식에 맞춰 예쁘게 출력한다!

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

# (시작 위치, 방향, 길이) 인자로 넘기면 재귀로 도미노 넘기기
def domino(sr, sc, sd, length):
    global temp
    if board[sr][sc]:
        board[sr][sc] = 0
        temp += 1
    for dis in range(length-1):
        sr += dirInfo[sd][0]
        sc += dirInfo[sd][1]
        if not (0 <= sr < N and 0 <= sc < M):
            continue
        domino(sr, sc, sd, board[sr][sc])

# main
N, M, R = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
raw = [row[:] for row in board]
dirInfo = {'E': (0, 1), 'W': (0, -1), 'S': (1, 0), 'N': (-1, 0)}

total = 0	# 넘어뜨린 도미노 갯수 총합
for game in range(R):
    off_r, off_c, off_d = input().split()
    def_r, def_c = map(int, input().split())
    off_r = int(off_r) - 1
    off_c = int(off_c) - 1
    def_r -= 1
    def_c -= 1

    # 공격 : 도미노 넘기기
    temp = 0
    if board[off_r][off_c]:
        domino(off_r, off_c, off_d, board[off_r][off_c])

    # 수비 : 도미노 세우기
    board[def_r][def_c] = raw[def_r][def_c]
    total += temp

# 정답 출력
print(total)
for r in range(N):
    for c in range(M):
        if board[r][c]:
            board[r][c] = "S"
        else:
            board[r][c] = "F"
    print(*board[r])

---

• 시간 : 216ms / 메모리 : 126004kb
• 고찰 : 한 번에 문제 이해를 하지 못해 시간을 많이 잡아먹었다.. 실전에서 절대 이러지 않도록 연습을 더 많이 해야겠다. 쉬운 문제라고 방심한 것이 한시간 반을 버리게 만들었다. 결과적으로 한 40분 정도면 충분히 풀 수 있었던 문제인 것 같다. 한번에 잘 이해하고 손으로 머리로 설계하고 코드로 옮기자!