[BOJ/백준] 23290 마법사 상어와 복제 파이썬

문제 링크 : https://www.acmicpc.net/problem/23290

23290번: 마법사 상어와 복제

 

백트래킹, 구현 문제이다.

문제에 요구하는게 많아서 소스가 길어졌다.

 

우선 나는 물고기가 저장된 배열, 냄새를 표시한 배열 두개를 사용 했다.

물고기를 저장한 배열은 2개의 원소를 갖는다.

 

0번째 현재 해당칸에 있는 물고기

1번째 복제될 물고기

그래서 문제의 5번단계에서 1번째 값의 물고기들을 0번째 값에 추가해줬다.

 

냄새를 표시한 배열은 물고기가 이동할 때 해당 배열을 검사 후 진행한다.

 

나는 문제 작업 그대로 구현했다.

 

1. 상어 복제 시작

물고기 배열의 첫번째 값을 두번째 값에 넣어줬다.

 

2. 물고기 이동

물고기가 동시에 이동하므로 이동한 물고기를 따로 배열로 만들어 준후 다시 물고기 배열을 갱신했다.

물고기 이동은 8방향 탐색을 하는데 현재 방향으로 못가면 시계반대방향으로 회전하면 된다.

만약 이동할 칸을 못찾았다면 현재 칸에 머무른다.

그래서 이동을 마쳤다면 해당 좌표정보와 방향정보를 임시저장하고 리턴해준다.

 

다음 리턴해준 정보를 바탕으로 물고기 배열의 값을 갱신한다.

 

3. 상어 이동

우선 상어가 이동할 방향을 골라주자.

백트래킹, dfs로 구현해보면 된다.

이때 주의할 건 갔던 방향으로 다시 돌아와도 된다.

 

대신 한번 들렀던 칸이므로 물고기를 카운팅 해주면 안된다.

이부분을 놓쳐서 틀렸었다.

 

그래서 방문체크를 해주자.

만약 방문 하지 않았고 물고기가 있다면 물고기를 세주고

없다면 그냥 가자.

 

3번 다 이동 했다면 경로와 최대물고기양을 갱신해주자.

근데 우선순위가 있다.

하지만 방향을 선택할 때 방향의 값 순서대로 선택하면 값이 작은것 순으로 고르는 것이므로 따로 우선순위를 체크안해줘도 된다.

 

상어 이동 방향을 구했다면 그대로 이동해주자.

이때 물고기가 있는 칸이라면 해당칸 물고기를 없애주고 냄새 배열의 현재 칸에 값을 3으로 설정하자.

3으로 한 이유는 바로 다음 단계에서 냄새를 -1 해주기 때문이다.

 

 

4. 냄새 조정

0 이상인 냄새 값을 -1 해주자.

 

5. 물고기 복제 완료

물고기 배열의 두번째 값을 이제 첫번째 값에다 넣어주자.

 

s번만큼 수행 후 이제 물고기 배열의 첫번째에 들어있는 물고기를 세주면 끝이다.

 

from sys import stdin
from collections import deque

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

sdx = [-1,0,1,0]
sdy = [0,-1,0,1]

input = stdin.readline

m,s = map(int, input().split())
fish_board = [[[[],[]] for _ in range(4)] for _ in range(4)]
smell_board = [[0]*4 for _ in range(4)]
for _ in range(m):
    x,y,d = map(int, input().split())
    fish_board[x-1][y-1][0].append(d-1)

sx,sy = map(int, input().split())
sx-=1
sy-=1
path = []
max_fish_count = -1

visited = [[False]*4 for _ in range(4)]
def solv():
    global path, max_fish_count
    for now in range(s):
        start_copy_fish()

        move_target = move_fish()
        renew_fish_board(move_target)

        path = []
        max_fish_count = -1

        select_move_shark_path(sx,sy,0,0,[])
        move_shark()

        reduce_smell()

        end_copy_fish()
    answer = 0
    for x in range(4):
        for y in range(4):
            answer += len(fish_board[x][y][0])
    print(answer)
def reduce_smell():
    global smell_board
    for x in range(4):
        for y in range(4):
            if smell_board[x][y] > 0:
                smell_board[x][y] -= 1
def move_shark():
    global sx,sy,fish_board,smell_board
    for d in path:
        sx += sdx[d]
        sy += sdy[d]
        if fish_board[sx][sy][0]:
            fish_board[sx][sy][0] = []
            smell_board[sx][sy] = 3
def select_move_shark_path(x,y,fish_count,move_count,tmp_path):
    global sx,sy,visited, max_fish_count, path
    if move_count == 3:
        if max_fish_count < fish_count:
            max_fish_count = fish_count
            path = [d for d in tmp_path]
        return
    for d in range(4):
        nx = x + sdx[d]
        ny = y + sdy[d]
        if boundary_validator(nx,ny):
            if not visited[nx][ny]:
                visited[nx][ny] = True
                nxt_fish_count = fish_count + len(fish_board[nx][ny][0])
                select_move_shark_path(nx,ny,nxt_fish_count,move_count+1,tmp_path+[d])
                visited[nx][ny] = False
            else:
                select_move_shark_path(nx,ny,fish_count,move_count+1,tmp_path+[d])

def renew_fish_board(move_target):
    global fish_board
    for x,y,nd in move_target:
        fish_board[x][y][0].append(nd)
def move_fish():
    move_target = []
    for x in range(4):
        for y in range(4):
            while fish_board[x][y][0]:
                nd = fish_board[x][y][0].pop()
                flag = False
                for _ in range(8):
                    nx = x + dx[nd]
                    ny = y + dy[nd]
                    if point_validator(nx,ny):
                        move_target.append((nx,ny,nd))
                        flag = True
                        break
                    nd = (nd - 1) % 8
                if not flag:
                    move_target.append((x, y, nd))
    return move_target
def boundary_validator(x,y):
    if x < 0 or y < 0 or x >= 4 or y >= 4:
        return False
    return True

def point_validator(x,y):
    if not boundary_validator(x,y):
        return False
    elif smell_board[x][y] != 0:
        return False
    elif (x,y) == (sx,sy):
        return False
    return True

def start_copy_fish():
    for x in range(4):
        for y in range(4):
            for d in fish_board[x][y][0]:
                fish_board[x][y][1].append(d)
def end_copy_fish():
    global fish_board
    for x in range(4):
        for y in range(4):
            while fish_board[x][y][1]:
                fish_board[x][y][0].append(fish_board[x][y][1].pop())
solv()