[백준 23290번] 마법사 상어와 복제(파이썬)

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

23290번: 마법사 상어와 복제

저 같은 경우에는

상어이동때문에

애를 많이 먹었습니다.

저거 때문에 예시 하나가 안 풀려서

솔루션까지 참고했는데

제가 틀린 것을 발견하는데 상당히 애를 먹었습니다.

 

1. 물고기이동

 

저는 별도의 temp리스트에서

물고기가 이동하는 케이스를 받았습니다.

원래 상어는 graph에 두고

temp에 물고기가 이동하는 걸 그려넣었습니다.

 

2.  상어이동

 

노트를 꼼꼼히 봐야하는 문항.

우선 순위가

상 좌 하 우 입니다.

물고기 이동에서 냅둔 이동값으로

우선순위를 정해도 되지만,

그냥 맘 편하게 상어에 대한 이동을

따로 정리해주는 것도 좋습니다.

 

코테를 어느정도 풀어보신 분들이라면

상어이동은 DFS로 풀 수 있다는 걸 떠올릴 수 있습니다.

 

https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-14888%EB%B2%88-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0

[백준 14888번] 연산자 끼워넣기

 

https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-15683%EB%B2%88-%EA%B0%90%EC%8B%9C%ED%8C%8C%EC%9D%B4%EC%8D%AC-1

[백준 15683번] 감시(파이썬)

이런 류의 문제를 참고하시면 이해가 쉽습니다.

 

상어를 3번이동하는데

이 때, 물고기를 얼마를 먹고

그 중 물고기를 가장 많이 먹는 경우를 구해야합니다.

그럼 범위 안 벗어나는지 확인하고

visited로 방문한데 안가면 되는 거잖아....

하다가 이 문제의 노트를 보면

상어가 이동하면서

제자리로 오는 경우도 가능합니다.

위의 그림처럼

좌 우 상

한번 제자리를 찍고 위를 가는

그런 케이스도 가능하죠.

 

여기서 가장 난감한 부분은

'물고기를 먹는 경우'까지 봐야하는 것.

예시케이스로

우 좌 우

이렇게 간다고 치겠습니다.

오른쪽에 물고기가 하나 있어 이동했습니다.

그 뒤, 제자리로 간 다음에

다시 오른쪽으로 갈 때에는

물고기를 이미 먹은 상황이므로

물고기를 먹은 걸로 계산해서는 안 됩니다.

여기서 실수로

'그럼 물고기 먹었으니

물고기 자리를 없애야지!'라고 하면

그 뒤에 물고기 자리를 구하는 케이스를

제대로 구하기 힘든 상황.

 

그래서 이 문제를 풀 때에는

1. 방문한 곳도 또 방문가능하도록

2. 다만, 물고기가 있었던 곳은 visited로 표시하고 

visited가 있으면 그 격자의 물고기 수를 더함.

3. 만약 visited로 체크가 안되면 물고기는 더하지 않음.

 

 

3. 냄새

 

별도의 냄새 리스트를 만들어줍니다.

2에서 물고기를 최대로 먹는

이동경로대로 상어를 이동시키면서

물고기가 있는 격자는 clear시켜주고

그 자리에 해당하는 냄새 리스트에

+3을 추가합니다.

그리고, 냄새 리스트에서

0보다 큰 요소값을 -1해줍니다.

그럼 처음에 들어간 건 2가 되고

계속 빼지다보면 0이 됩니다.

 

4. 상어 복사완료

 

graph리스트에

temp 리스트를 append 시켰습니다.

temp리스트를 돌다가, temp에 뭔가 있는 걸 발견하면

해당 지점 graph에 append 시킵니다.

 

# 백준 23290 마법사 상어와 복제
from copy import deepcopy
from sys import stdin

M, S = map(int, input().split())

graph = [[[] for _ in range(4)] for _ in range(4)]
smell = [[0] * 4 for _ in range(4)]

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

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

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

s_x, s_y = map(int, input().split())
s_x -= 1
s_y -= 1

moving = []


def shark_move(depth, now_fish, x, y, tmp_path):
    global moving
    global max_fish
    global move
    if depth == 3:
        if now_fish > max_fish:
            max_fish = now_fish
            moving = [d for d in tmp_path]

        return

    for d in range(4):
        nx = x + s_direct[d][0]
        ny = y + s_direct[d][1]

        if nx < 0 or nx >= 4 or ny < 0 or ny >= 4:
            continue
        # 상어는 갔던 길 다시 돌아갈 수 있다
        # 상하상 이렇게 갈 수 있다는 걸 명시!!!
        if visited[nx][ny] == False:
            visited[nx][ny] = True
            shark_move(depth + 1, now_fish + len(temp[nx][ny]), nx, ny, tmp_path + [d])
            visited[nx][ny] = False
        else:
            shark_move(depth + 1, now_fish, nx, ny, tmp_path + [d])


time = 1
while time <= S:

    # 1.물고기를 먼저 이동시킨다.
    temp = [[[] for _ in range(4)] for _ in range(4)]
    for x in range(4):
        for y in range(4):
            if graph[x][y]:
                for index in range(len(graph[x][y])):
                    go = 0
                    change = 0
                    o_d = graph[x][y][index]
                    f_d = graph[x][y][index]
                    while change < 8:
                        nx = x + direct[f_d][0]
                        ny = y + direct[f_d][1]
                        # 격자벗어나는지 확인
                        if nx < 0 or nx >= 4 or ny < 0 or ny >= 4:
                            f_d = (f_d - 1) % 8
                            change += 1
                        # 냄새있는지 확인
                        elif smell[nx][ny] > 0:
                            f_d = (f_d - 1) % 8
                            change += 1
                        # 상어랑 겹치는지 확인
                        elif nx == s_x and ny == s_y:
                            f_d = (f_d - 1) % 8
                            change += 1
                        else:
                            go = 1
                            temp[nx][ny].append(f_d)
                            break

                    # 8번이나 방향을 바꾸었으면, 이동x
                    if not go == 1:
                        temp[x][y].append(o_d)

                    # 그게 아니라면, 이동해준다.
                    if go == 1:
                        continue

    # 2상어가 이동한다
    max_fish = -1
    moving = []
    visited = [[False] * 4 for _ in range(4)]
    shark_move(0, 0, s_x, s_y, [])

    for go in moving:
        s_x += s_direct[go][0]
        s_y += s_direct[go][1]
        # print(s_x,s_y)
        if temp[s_x][s_y]:
            temp[s_x][s_y].clear()
            smell[s_x][s_y] = 3

    # 3. 2번전 생긴 물고기 냄새는 사라진다.
    for x in range(4):
        for y in range(4):
            if smell[x][y] > 0:
                smell[x][y] -= 1

    # 4. 물고기 모두 복제.
    for x in range(4):
        for y in range(4):
            if temp[x][y]:
                for i in range(len(temp[x][y])):
                    graph[x][y].append(temp[x][y][i])

    time += 1

fish_num = 0
for x in range(4):
    for y in range(4):
        if graph[x][y]:
            fish_num += len(graph[x][y])

print(fish_num)

 

https://westmino.tistory.com/137?category=882388 

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

제가 참고했던 풀이입니다.

 

이동에 대한 부분이 뭔가 불친절했지만...

문제를 꼼꼼하게 봐야겠네요.

특히나, 상어를 이동시킬 때

물고기를 먹은 다음에는

어떻게 케이스를 구할지 생각하게 해준

공부할 거리가 많았던 문제였습니다.

 

+++++

개선된 풀이입니다.

#백준 23290

graph=[[[]for _ in range(4)] for _ in range(4)]


M,S=map(int,input().split())

smell=[[0]*4 for _ in range(4)]

for i in range(M):
    x,y,d=map(int,input().split())
    x-=1
    y-=1
    d-=1
    graph[x][y].append(d)

sx,sy=map(int,input().split())
sx-=1
sy-=1

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

s_x=[-1,0,1,0]
s_y=[0,-1,0,1]

def shark_move(x,y,num,total,tmp):
    global max_fish,case,visited
    if num==3:
        if max_fish<total:
            max_fish=total
            case=[d for d in tmp]
        return
    for d in range(4):
        nx=x+s_x[d]
        ny=y+s_y[d]

        if nx<0 or nx>=4 or ny<0 or ny>=4:
            continue

        if not visited[nx][ny]:
            visited[nx][ny]=True
            shark_move(nx,ny,num+1,total+len(temp[nx][ny]),tmp+[d])
            visited[nx][ny]=False
        else:
            shark_move(nx,ny,num+1,total,tmp+[d])

for turn in range(S):
    #물고기가 복사되어 이동한다
    temp=[[[]for _ in range(4)] for _ in range(4)]
    for x in range(4):
        for y in range(4):
            if graph[x][y]:
                #격자에 물고기가 존재할 경우에 물고기 이동
                for fish in graph[x][y]:
                    flag=0
                    t_fish=fish
                    #8방향으로 돌아간다는 개념
                    for _ in range(8):
                        nx=x+dx[fish]
                        ny=y+dy[fish]
                        #범위
                        if nx<0 or nx>=4 or ny<0 or ny>=4:
                            fish=(fish-1)%8

                            continue
                        #상어
                        if nx==sx and ny==sy:
                            fish = (fish - 1) % 8
                            continue
                        #냄새
                        if smell[nx][ny]>0:
                            fish = (fish - 1) % 8
                            continue
                        #저 조건을 다 벗어나면 돌아가고 다음걸로 간다
                        temp[nx][ny].append(fish)
                        flag=1
                        break
                    if flag==0:
                        temp[x][y].append(t_fish)
    #상어이동-3번이동-->dfs활용
    case=[]
    max_fish=-1
    visited=[[False]*4 for _ in range(4)]
    shark_move(sx,sy,0,0,[])
    #가장 많이 먹는 케이스대로 움직인다.+가장 먼저 순
    #중간에 물고기있으면 그 물고기 다 먹고, 그 위치에 냄새를 남긴다
    for m in case:
        sx+=s_x[m]
        sy+=s_y[m]
        if temp[sx][sy]:
            temp[sx][sy]=[]
            smell[sx][sy]=3
    #냄새를 지운다
    #원래 물고기들 합치기
    for x in range(4):
        for y in range(4):
            if smell[x][y]>0:
                smell[x][y]-=1
            if temp[x][y]:
                graph[x][y]=graph[x][y]+temp[x][y]
answer=0
for x in range(4):
    for y in range(4):
        if graph[x][y]:
            answer+=len(graph[x][y])


print(answer)

개선점

 

1. 방향돌려주는 거 for 문으로 변경

2. graph와 temp를 합칠 때, 같은 리스트라는 점을 이용해서

+로 합쳐줌.

 

*주의사항

1. 내가 제대로 변수를 잘 적었나?

-->2번째 풀이시, 물고기 이동조건에서

nx==sx and ny==sx

라고 적어서 한참을 해매었다.

만약 문제가 뭔가 잘못되었다면

내가 변수를 뭘 잘못먹은 게 아닐까 다시 접근한다.

 

2. 조건에 맞게 적었나?

-->2번쨰 풀이시 제출했더니

15%에서 막혔다.

이전의 풀이와 비교한 결과

상어가 이동할 때

smell[nx][ny]=3

이렇게 해야하는 걸

smell[nx][ny]+=3

이렇게 해버렸다.

이런 거 하나 하나 주의하자.

 

(추가 업데이트-2022.10.12)

from itertools import product
f_dir=[(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1)]
s_dir=[(-1,0),(0,-1),(1,0),(0,1)]


M,S=map(int,input().split())
room=[[[]for _ in range(4)] for _ in range(4)]
smell=[[-3]*4 for _ in range(4)]
for _ in range(M):
    x,y,d=map(int,input().split())
    room[x-1][y-1].append(d-1)


def inside(x,y):
    if x<0 or x>=4 or y<0 or y>=4:
        return False
    return True

sx,sy=map(int,input().split())
sx-=1
sy-=1

time=0
for time in range(S):
    # print(time)
    # print(sx,sy)
    # for x in range(4):
    #     print(room[x])
    # print()
    temp=[[[]for _ in range(4)]for _ in range(4)]

    #1 물고기 이동
    #이동한 걸 temp배열에 추가해준다
    for x in range(4):
        for y in range(4):
            if room[x][y]:

                for nd in room[x][y]:
                    flag=False
                    now=nd
                    for d in range(8):
                        nx=x+f_dir[now][0]
                        ny=y+f_dir[now][1]

                        if inside(nx,ny) and  not [nx,ny]==[sx,sy] and smell[nx][ny]+2<time:
                            temp[nx][ny].append(now)
                            flag=True
                            break
                        now=(now-1)%8
                    #아무데도 못간다-->그 자리에 넣어준다
                    if not flag:
                        temp[x][y].append(nd)
    # for x in range(4):
    #     print(temp[x])
    # print()
    #2. 상어이동
    #중복조합으로 케이스를 미리 구한거에다가 넣어보자
    #max를 -1로 초기화한 이유-->어떤 케이스로 움직이든 하나도 못먹는 케이스 존재
    #만약 0으로 초기화를 해놓으면, 만약 아무것도 못먹으면 상어가 움직이지 않는다
    #그러니, 0이 될 때에 가장 사전순인 상상상이라도 받도록 해준다
    eat_max=-1
    go=[]
    for case in list(product([0, 1, 2, 3], repeat=3)):

        tx=sx
        ty=sy
        t_fish=0
        flag=False
        move=set()
        for num in case:

            tx+=s_dir[num][0]
            ty+=s_dir[num][1]

            #범위벗어나면 넘김
            if not inside(tx,ty):
                flag=True
                break
            if not (tx,ty) in move:
                t_fish+=len(temp[tx][ty])
                move.add((tx,ty))

        if flag:
            continue

        if eat_max<t_fish:
            eat_max=t_fish
            go=list(case)



    #3. 이동하면서 물고기 먹어준다
    for num in go:
        sx+=s_dir[num][0]
        sy+=s_dir[num][1]
        if temp[sx][sy]:
            smell[sx][sy]=time
        temp[sx][sy].clear()


    #이전에 복제한 거에 더해준다
    for x in range(4):
        for y in range(4):
            room[x][y]+=temp[x][y]

    # print()
    # for x in range(4):
    #     print(room[x])
    # print()

answer=0
for x in range(4):
    for y in range(4):
        if room[x][y]:
            answer+=len(room[x][y])

print(answer)

 

다시 풀이를 할 때에는

'중복조합'이라는 친구를 사용해봤습니다.

dfs로 일일이 지나가는 방식도 의미있는데

저렇게 중복조합으로 바꾸는 게

재귀를 안 써서 직관적으로 이해가 더 편합니다.

그리고 지나갔던 격자를 집합으로 받아서

집합안에 없으면 더하는 방식으로 개선했습니다.

 

냄새는 일일이 빼주기보다는

현 시점에서 물고기가 있는 지점에 냄새를 넣어주고

다음에 물고기가 이동할 때

'이 칸에 냄새를 넣은 지점+2<현재시점'이라면 지나가도록 만들었습니다.

 

다시 풀면서도 디버깅부분에서 애먹긴 했지만

풀어도 풀어도 공부할 게 많은 문제입니다.