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

문제

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

23290번: 마법사 상어와 복제

 

내 풀이

 

문제에서 구현하라고 하는 대로 구현하면 된다.

 

다 풀고나서 테스트를 해보았을 때, 몇 개의 테스트 케이스에서 답이 안 나왔다.

이유를 알아보니, 상어가 이동할 수 있는 3개의 칸을 구할 때, (1, 1) -> (1, 2) -> (2, 2) -> (1, 2)와 같이 이전에 방문했던 칸을 다시 방문할 수 있다는 조건을 따로 달아주지 않았던 것이었다.

이전 방문에서 물고기 수를 세었으므로 다시 방문할 때에는 물고기 수를 세는 과정을 패스해야 한다.

나는 if (nx, ny) not in can_go로 조건을 달아주었다.

 

import copy

M, S = map(int, input().strip().split())
grid = [[[] for _ in range(4)] for _ in range(4)]
for _ in range(M):
    fx, fy, d = map(int, input().strip().split())
    grid[fx-1][fy-1].append(d) # (fx, fx)에 있는 d 방향을 가진 물고기
sx, sy = map(int, input().strip().split())
sx -= 1
sy -= 1
dx, dy = [0, 0, -1, -1, -1, 0, 1, 1, 1], [0, -1, -1, 0, 1, 1, 1, 0, -1]
smell = [[0]*4 for _ in range(4)]
sdx, sdy = [0, -1, 0, 1, 0], [0, 0, -1, 0, 1]

def move_shark(cnt, dir, grid):
    global MAX, shark_go
    if cnt == 3:
        fish_num = 0
        can_go = []
        x, y = sx, sy
        for d in dir:  # [1, 2, 3]
            nx, ny = x + sdx[d], y + sdy[d]
            if 0 <= nx < 4 and 0 <= ny < 4:
                if (nx, ny) not in can_go:
                    fish_num += len(grid[nx][ny])
                can_go.append((nx, ny))
                x, y = nx, ny
            else:
                break
        if len(can_go) == 3:
            if MAX < fish_num:
                MAX = fish_num
                shark_go = can_go[:]
        return
    for i in range(1, 5):
        dir.append(i)
        move_shark(cnt + 1, dir, grid)
        dir.pop()

for _ in range(S):
    copy_grid = copy.deepcopy(grid)
    new_grid = [[[] for _ in range(4)] for _ in range(4)]

    for i in range(4):
        for j in range(4):
            if grid[i][j]: # 물고기가 1마리 이상 있으면
                for d in grid[i][j]:
                    move = False
                    nd = None
                    for k in range(8):
                        nd = (d-k)%8
                        if nd == 0: nd = 8
                        nx, ny = i+dx[nd], j+dy[nd]
                        if 0 <= nx < 4 and 0 <= ny < 4 and (nx, ny) != (sx, sy) and not smell[nx][ny]: # 범위에 들어가고, 상어가 있는 칸이 아니고, 물고기의 냄새가 없는 칸
                            new_grid[nx][ny].append(nd)
                            move = True
                            break
                    if not move:
                        new_grid[i][j].append(d)
    MAX = -1
    shark_go = [][:]
    move_shark(0, [], new_grid)
    sx, sy = shark_go[-1][0], shark_go[-1][1]

    for x, y in shark_go:
        if new_grid[x][y]:
            new_grid[x][y] = []
            smell[x][y] = 3

    for i in range(4):
        for j in range(4):
            if smell[i][j] > 0:
                smell[i][j] -= 1

    for i in range(4):
        for j in range(4):
            if copy_grid[i][j]:
                new_grid[i][j] += copy_grid[i][j]

    grid = copy.deepcopy(new_grid)

ans = 0
for i in range(4):
    for j in range(4):
        ans += len(grid[i][j])
print(ans)

 

총평

조건이 많아서 까다롭다.

함부로 조건을 넘기지 말자.