[백준] 23290번: 마법사 상어와 복제

문제 이동

소요시간 : 3시간 20분
체감 난이도 : 상
유형 : dfs, 구현, 그래프

어려웠던 것

• dfs 구현
  애초에 나는 dfs 백트래킹이 아직 익숙하지 않아서 어려웠다.
  사실은 단순하게 해당 depth에서 방문할 수 있는 반복문에 대해 visit 추가하고 dfs 재귀 돌리고 visit에서 빼고 하는 거다.

  참고 블로그
  https://ryu-e.tistory.com/107

감사합니다

• 오타
  실수로 r과 c를 반대로 써서 찾는 데 오래 걸렸다.

• 생선 이동
  생선을 이동시킬 때 이동할 칸이 없으면 제자리에 추가했어야 했는데 그걸 빼먹어서 고생했다.

느낀 점

• 문제를 이해하기 어렵긴 하지만 1번 ~ 5번으로 순서가 적혀있는 문제는 코드상에서 해당 순서대로 함수를 만들고 돌려보면서 수정하면 되는 것 같다.
• 다만 어이없는 실수를 하면 시간이 부족할 수도 있으니 처음 짤 때 정신차리고 짜야 한다.
• 노가다 디버깅할 때 보기 편하게 프린트해야 오히려 시간을 아끼는 것 같다.

코드

M, S = map(int, input().split())
fishes = []
for _ in range(M):
    r, c, d = map(int, input().split())
    fishes.append((r-1, c-1, d-1))
shark_r, shark_c = map(int, input().split())
shark_r -= 1
shark_c -= 1

dir = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]

board = [[[] for _ in range(4)] for _ in range(4)]
# [[[],[],[],[]],[[],[],[],[]],...]
for r, c, d in fishes:
    board[r][c].append(d)


def move_fishes(fishes, smells):
    global tmp
    # print("smells", smells)
    smell = sum(smells, [])
    for r, c, d in fishes:
        d = (d + 8) % 8
        flag = False
        for _ in range(8):
            # print(d)
            nr, nc = r + dir[d][0], c + dir[d][1]
            if 0 <= nr< 4 and 0 <= nc < 4 and (nr, nc) != (shark_r, shark_c) and (nr, nc) not in smell:
                tmp[nr][nc].append(d)
                flag = True
                # if r == 1 and c == 0:
                #     print(nr, nc)
                break
            else:
                d -= 1
        if not flag:
            tmp[r][c].append(d)

def dfs(r, c, depth, cnt, visit):
    global max_rm, shark_c, shark_r, visited
    # print(r, c, depth)
    if depth == 3:
        if cnt > max_rm:
            max_rm = cnt
            shark_r, shark_c = r, c
            visited = visit[:]
        return

    for d in range(4):
        nr, nc = r + dr[d], c + dc[d]
        if 0 <= nr < 4 and 0 <= nc < 4:
            if (nr, nc) not in visit:   # 해당 칸 첫 방문 -> 물고기 제거 수 추가
                visit.append((nr, nc))
                dfs(nr, nc, depth + 1, cnt + len(tmp[nr][nc]), visit)
                visit.pop()
            else:                       # 재방문 -> 제거할 물고기가 없음
                dfs(nr, nc, depth + 1, cnt, visit)

dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]

smells = []
for _ in range(S):
    smell = []
    visited = []
    max_rm = -1
    # 1. 복제 마법 시전
    tmp = [[[] for _ in range(4)] for _ in range(4)]
    # 2. 물고기 이동 (tmp)
    move_fishes(fishes, smells)
    # print("물고기 이동 : ", tmp)
    # 3. 상어 이동
    dfs(shark_r, shark_c, 0, 0, [])
    # 지나온 경로 물고기 사라짐.
    for vr, vc in visited:
        if tmp[vr][vc]:
            tmp[vr][vc] = []
            smell.append((vr, vc))
    # print("smell", smell)
    smells.append(smell)
    # 4. 냄새 사라짐
    if len(smells) > 2:
        smells = smells[-2:]
    # 5. 복제 & 새로운 fishes
    fishes = []
    for r in range(4):
        for c in range(4):
            # print(board[r][c], tmp[r][c])
            board[r][c].extend(tmp[r][c]) # [d] + [td, td2]
            for d in board[r][c]:
                fishes.append((r, c, d))
    # print("복제 후 : ", board)
    # print("-" * 50)

answer = 0
for r in range(4):
    for c in range(4):
        if board[r][c]:
            answer += len(board[r][c])
# print("Answer================================")
print(answer)