[백준 19236번] 청소년 상어(파이썬)

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

19236번: 청소년 상어

난이도 대비 정답률은 높았던 문제.

아마 널리 알려진 기출이라

'풀이보고 적어서 내야지'

하는 사람이 많았나...하는 예상이 듭니다만...

이 문제가 풀려있고

정답률도 60%대이길래

어 겁나 쉬운가보구나...

했더니 낑낑댔습니다.

문제 난이도 확인했더니 골드2....

 

이 문제에서 구해줘야할 것은 다음과 같습니다.

 

1. 상어가 물고기 먹기

 

2. 물고기 이동

 

3. 상어가 이동

;

여기서 난이도가 빡센 것이 바로 3번.

3번은 DFS+백트레킹이 같이 되는 부분인데

이 크기가 상당히 거대해서 어렵게 느껴졌습니다.

 

백트래킹 할 것이 이렇게 큽니다.

그래서 상대적으로 이부분에 대해서

코드 구현이 상당히 어려웠습니다.

저는 나동빈님이 쓰신

이것이 코딩테스트다를 참고하여

코드를 정리했습니다.

 

import copy
array=[[None]*4 for _ in range(4)]

for i in range(4):
    data=list(map(int, input().split()))
    for j in range(4):
        array[i][j]=[data[j*2],data[j*2+1]-1]


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

def turn_left(direction):
    return (direction+1)%8

result=0

def find_fish(array,index):
    for i in range(4):
        for j in range(4):
            if array[i][j][0]==index:
                return (i,j)
    return None

def move_all_fishes(array,now_x,now_y):
    for i in range(1,17):
        position=find_fish(array,i)
        if position!=None:
            x,y=position
            direction=array[x][y][1]
            for j in range(8):
                nx=x+dx[direction]
                ny=y+dy[direction]

                if 0<=nx<4 and 0<=ny<4:
                    if not (nx==now_x and ny==now_y):
                        array[x][y][1]=direction
                        array[x][y],array[nx][ny]=array[nx][ny],array[x][y]
                        break
                direction=turn_left(direction)

def get_possible_po(array,now_x,now_y):
    positions=[]
    direction=array[now_x][now_y][1]

    for i in range(4):
        now_x+=dx[direction]
        now_y+=dy[direction]

        if 0<=now_x<4 and 0<=now_y<4:
            if array[now_x][now_y][0]!=-1:
                positions.append([now_x,now_y])
    return positions


def dfs(array,now_x,now_y,total):
    global result
    array=copy.deepcopy(array)

    total+=array[now_x][now_y][0]
    array[now_x][now_y][0]=-1

    move_all_fishes(array,now_x,now_y)

    positions=get_possible_po(array,now_x,now_y)

    if len(positions)==0:
        result=max(result,total)
        return

    for next_x,next_y in positions:
        dfs(array,next_x,next_y,total)

dfs(array,0,0,0)
print(result)

https://chldkato.tistory.com/181

백준 19236 청소년 상어 (파이썬)

나동빈님 같은 경우에는

상어가 이동할 수 있는 경우를 모두 담은 후에

상어가 이동하는 방식을 취했습니다.

반면에, 직접 상어를 움직이면서

백트레킹을 시행하는 방식도 존재합니다.

어느쪽이든 간에, 공부할 요소가 많은 문제입니다.

 

+++

2022.10.11 추가 업데이트

from copy import deepcopy

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

room=[list(map(int,input().split())) for _ in range(4)]
fish=[[] for _ in range(17)]
direct=[0]*17
water=[[0]*4 for _ in range(4)]
#0 먼저 물고기의 움직임 받아줌
for x in range(4):
    for y in range(4):
        f_num=room[x][2*y]
        f_d=room[x][2*y+1]
        water[x][y]=f_num
        fish[f_num]=[x,y]
        direct[f_num]=f_d-1

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

def dfs(sx,sy,fish,direct,water,total_eat):
    global answer

    #현재 좌표의 물고기를 먹고 그 물고기의 방향 받아준다
    # 물고기를 pop해버리면 순서가 꼬이니
    #다 먹은 건 [-1,-1] 로 처리해준다
    eat=fish.index([sx,sy])
    sd = direct[eat]
    next_total=total_eat+eat
    water[sx][sy]=0
    fish[eat] = [-1, -1]

    direct[eat] = -1

    #1.물고기 이동먼저
    for i in range(1,17):
        #이미 없어진 물고기는 넘긴다
        if fish[i]==[-1,-1]:
            continue
        fx,fy=fish[i]
        fd=direct[i]
        for _ in range(8):
            nx=fx+dir[fd][0]
            ny=fy+dir[fd][1]

            #범위를 벗어나거나 상어가 있다면 방향을 튼다
            if not inside(nx,ny):
                fd=(fd+1)%8

                continue

            if [nx,ny]==[sx,sy]:
                fd=(fd+1)%8

                continue

            #만약 빈 공간이라면
            if water[nx][ny]==0:
                #print('black')
                fish[i]=[nx,ny]
                water[nx][ny], water[fx][fy] = water[fx][fy], water[nx][ny]
                direct[i] = fd
                break
            elif water[nx][ny]>0:
                #print('change')
                c_fish=fish.index([nx,ny])
                fish[i]=[nx,ny]
                fish[c_fish]=[fx,fy]
                water[nx][ny],water[fx][fy]=water[fx][fy],water[nx][ny]
                direct[i] = fd
                break

        # if i==8:
        #     print(direct[i])

    # if next_total==33:
    #     print(eat)
    #     print(sx,sy,sd)
    #     print(water)
    #     print(fish)

    #상어의 이동을 본다
    # print(next_water)
    # print(next_fish)
    # print(next_direct)

    nfx=sx
    nfy=sy
    while True:
        nfx+=dir[sd][0]
        nfy+=dir[sd][1]
        if not inside(nfx,nfy):
            break
        if water[nfx][nfy]==0:
            continue
        next_fish = deepcopy(fish)
        next_direct = deepcopy(direct)
        next_water = deepcopy(water)

        dfs(nfx,nfy,next_fish,next_direct,next_water,next_total)

    answer=max(answer,next_total)
    return

dfs(0,0,fish,direct,water,0)
print(answer)

 

다시 푼 방식입니다.

이번에는 water에다가는 물고기 번호를 적고

fish에는 번호별 물고기 좌표

direct에는 번호별 물고기 방향

이렇게 넣고 백트레킹했습니다.

다 구하고 맞왜틀 반복했는데

그 이유는'상어가 물고기가 없는 곳은 이동하지 않는다'

라는 조건 때문이었습니다.

저는 이 부분을 break해줬는데

continue해야 맞더군요.

2022.10.07 - [알고리즘 공부] - [코드트리] 나무박멸(파이썬) -2022 삼성sw 상반기 코테 기출

[코드트리] 나무박멸(파이썬) -2022 삼성sw 상반기 코테 기출

이 문제가 자연스럽게 떠올랐습니다.

이 문제도 살충제가 

'나무가 비어있는 곳까지 가고

그 이후론 안간다'라는 문구가 숨어져있어

이를 파악하는데 제법 오래 걸렸습니다.

이 문제도 이처럼

물고기가 없으면 이동을 안한다했지

아예 이동자체를 멈춘다고는 안했습니다.

시험장에서 이런 류의 문제가 있을 때

한번 질문해봐야겠네요...

실전에서는 깜빡하다가 놓쳐서 맞왜틀 무한 반복할듯.