[문제풀이-백준] 19236. 청소년 상어

풀이

시뮬레이션

구현 방법

• 준비
  • 물고기의 좌표와 방향 정보를 저장하기 위한 딕셔너리
    • 여러 정보를 저장해야하므로 리스트보다는 딕셔너리가 낫다고 판단
  • 방향 정보를 담는 direct 리스트
• 상어가 (0,0)으로 들어와서 물고기를 먹음
• 함수
  • 물고기가 이동
    • 이동할 자리에 물고기가 없을 경우
      • 이동
      • 원래 자리는 0으로 변경
    • 이동할 자리에 물고기가 있을 경우
      • 물고기 딕셔너리 정보 교환
      • matrix 정보 교환
  • 상어 이동
    • 상어의 진행 방향에 물고기가 있을 경우
      • 재귀 전에 원래의 물고기 정보와 matrix 정보 저장해야함
        • 재귀에서 돌아오면 원래 정보로 되돌려 놓기 위해
      • 물고기 먹음
      • 재귀
      • 물고기 정보 martix정보 원래대로 되돌리기
      • 물고기 먹은거 취소
• 최댓값 찾기

잘못 생각한 점

• 상어가 이동할 때, 진행 방향의 물고기 중 가장 최댓값 물고기를 먹어야하는 줄 알았음

팁

• 딕셔너리 복사

  • 일반적인 키-값 쌍으로 이루어진 딕셔너리는 ~.copy()로 깊은 복사 가능
  • 값에 딕셔너리나 리스트 형태가 있다면 copy.deepcopy(~)해줘야함

• 딕셔너리나 리스트의 경우, 함수 밖에 선언 되있다면 전역 변수처럼 쓸 수 있는데 copy를 이용하면 함수 내에서 쓸 수 없음 => 인자로 계속 전달해야함

전체 코드

import copy

def play(r,c,sd,answer,fish,matrix):
    global ans
    # 물고기 이동
    for n, lst in fish.items():
        if not visited[n]:
            y, x, d = lst
            nd = d
            isFirst = True
            while isFirst or nd != d:
                isFirst = False
                ny, nx = y + direct[nd][0], x + direct[nd][1]
                if 0 <= ny < 4 and 0 <= nx < 4 and matrix[ny][nx] != -1:
                    if matrix[ny][nx] == 0:  # 비어있을 때
                        matrix[ny][nx] = n
                        fish[n][0], fish[n][1], fish[n][2] = ny, nx, nd
                        matrix[y][x] = 0
                    else:  # 다른 물고기가 있을 때
                        o = matrix[ny][nx]
                        fish[n][0], fish[o][0] = fish[o][0], fish[n][0]
                        fish[n][1], fish[o][1] = fish[o][1], fish[n][1]
                        fish[n][2] = nd
                        matrix[ny][nx] = matrix[y][x]
                        matrix[y][x] = o
                    break
                nd = (nd + 1) % 8

    # 상어 이동
    isFail = True
    for i in range(3):
        ny, nx = r + direct[sd][0] + direct[sd][0]*i, c + direct[sd][1]+direct[sd][1]*i
        if 0 <= ny < 4 and 0 <= nx < 4 and matrix[ny][nx] > 0:
            isFail = False
            t_matrix = copy.deepcopy(matrix)
            matrix[r][c] = 0
            n = matrix[ny][nx]
            visited[n] = True  # 잡아 먹힌 물고기
            matrix[ny][nx] = -1
            t_fish = copy.deepcopy(fish)
            play(ny,nx,fish[n][2],answer+n,fish,matrix)

            fish = copy.deepcopy(t_fish)
            matrix = copy.deepcopy(t_matrix)
            visited[n] = False  # 잡아 먹힌 물고기

    if isFail:
        if answer > ans:
            ans = answer


lst = [list(map(int,input().split())) for _ in range(4)]
fish = {i:[] for i in range(17)} # 물고기 번호별 좌표,방향 정보
visited = [False]*17
matrix = [[0]*4 for _ in range(4)] # 물고기 번호
direct = [(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]
for i in range(4):
    for j in range(4):
        number,D = lst[i][2*j],lst[i][2*j+1]
        matrix[i][j] = number
        fish[number].append(i)
        fish[number].append(j)
        fish[number].append(D-1)

visited[0] = True
ans = 0
first_fish = matrix[0][0]
matrix[0][0] = -1
visited[first_fish] = True
play(0,0,fish[first_fish][2],first_fish,fish,matrix)

print(ans)