[python] 19236 - 청소년 상어

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

19236번: 청소년 상어

 

정답률 63.295%

난이도 골2

물고기 정보를 따로 저장해놓는게 시간 절약

 

---

코드 설명

1. 입력 받기

2. 물고기 이동

3. 상어 이동 및 물고기 냠냠

 

 

※ 주의할 점

• fish는 물고기 위치 정보
• global_map은 위치별 (물고기 크기, 방향정보)
• dfs쓸때 서로 영향 주지 않게 fish와 global_map은 copy해서 쓰기
  - dfs 다시 불러오고 원위치 잊지 않기
• deepcopy보다 슬라이싱을 이용한 깊은 복사가 빠름
• for문보다 while break가 빠름

 

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

# 3. 상어 이동 및 물고기 냠냠
def dfs_shark(x, y, d, cnt):
    global ans, global_map, fish
    move_fish(x, y)
    while True:
        nx, ny = x + dx[d], y + dy[d] # 사냥 위치
        if not 0 <= nx < 4 or not 0 <= ny < 4:
            ans = max(ans, cnt)
            return
        if not global_map[nx][ny]:
            x, y = nx, ny
            continue

        temp_map = [dim[:] for dim in global_map]
        temp_fish = [dim[:] for dim in fish]

        fish[global_map[nx][ny][0]], global_map[nx][ny] = [], []
        dfs_shark(nx, ny, temp_map[nx][ny][1], cnt + temp_map[nx][ny][0] + 1)
        global_map, fish = temp_map, temp_fish
        x, y = nx, ny


# 2. 물고기 이동
def move_fish(sx, sy):
    for i in range(16):
        if fish[i]:
            x, y = fish[i][0], fish[i][1]
            ori_d = global_map[x][y][1]
            d = ori_d
            while True:
                nx, ny = x + dx[d], y + dy[d]
                if not 0 <= nx < 4 or not 0 <= ny < 4 or (sx == nx and sy == ny):
                    d = (d + 1) % 8
                    if d == ori_d:
                        break
                    continue
                if global_map[nx][ny]: #다른 물고기가 있다면
                    fish[global_map[nx][ny][0]] = [x, y]
                global_map[x][y] = global_map[nx][ny]
                global_map[nx][ny] = (i, d)
                fish[i] = [nx, ny]
                break



# 1. 입력 받기
global_map = [[] for _ in range(4)] # 맵
fish = [[] for _ in range(16)] # 물고기 순서대로 위치
ans = 0 # 답

for i in range(4):
    temp = list(map(int, input().split()))
    for j in range(0, 7, 2):
        global_map[i].append((temp[j]-1, temp[j+1]-1))
        fish[temp[j]-1] = [i, j//2]


d, cnt = global_map[0][0][1], global_map[0][0][0]
fish[cnt], global_map[0][0] = [], []
dfs_shark(0, 0, d, cnt + 1)
print(ans)

 

---

코드 결과