삼성전자 SW 코딩테스트, 마법사 상어와 복제

++ 어느 순간 부터 max_smell_dir 가 업데이트 되지 않아서 생기는 문제였는데, 이유를 발견하지 못했다ㅜㅜ 

 

입력 3번까지는 통과가 되는데, 4번부터 중간에 돌아가다가 멈춰서 주말에 한번 다시 풀어보도록 하겠다. 보니까 dfs로 푸시는 것 같아서 코드 싹 갈아엎고 dfs 문제 유형까지 정리할 예정

# 방향 이동 정의
def move(y, x, d):
    if 0<=d%8<=2:
        x-=1
    if 4<=d%8<=6:
        x+=1
    if 2<=d%8<=4:
        y-=1
    if 6<=d%8<=7 or d%8==0:
        y+=1
    return [y,x]
def move_shark(y,x,d):
    if d==1:
        y-=1
    if d==2:
        x-=1
    if d==3:
        y+=1
    if d==4:
        x+=1
    if 1<=x<=4 and 1<=y<=4:
        ok=1 # 가도 된다
    else:
        ok=0 # 갈 필요없다
    return [y,x,ok]

def practice(fish_loc, shark, smell):
    # 상어 복제 마법을 위한 현재 위치 저장
    fish_save = fish_loc[:]
    max_smell = [x[:2] for x in smell]
    # 모든 물고기가 한 칸 이동한다
    for i, (y, x, d) in enumerate(fish_loc):
        # 상어가 있는 칸, 물고기의 냄새 칸, 격자 밖이 아니라면
        while True:
            temp = move(y, x, d)
            if temp!=shark and temp not in max_smell and 0<temp[0]<=4 and 0<temp[1]<=4:
                fish_loc[i] = [temp[0],temp[1],d]
                break
            else:
                d-=1
                if d==0:
                    d=8

    # smell 업데이트
    for k, v in enumerate(smell):
        if smell[k][2] == 2:
            smell.remove(v)

    # 상어의 이동 (연속 3번)과 물고기 냄새
    # max_smell = [x[:2] for x in smell]
    max_smell_dir = []

    for i in range(4, 0, -1):
        for j in range(4, 0, -1):
            for k in range(4, 0, -1):
                temp_smell = []
                dir = [i, j, k]
                temp_shark = shark
                br=0
                temp_fish_loc = fish_loc[:]
                for q in range(3):
                    temp = move_shark(temp_shark[0], temp_shark[1], dir[q])
                    if temp[2] == 1:
                        for item in temp_fish_loc:
                            if item[:2] == temp[:2]:
                                temp_smell.append(item[:2])
                        for item in temp_fish_loc:
                            if item[:2] in temp_smell:
                                temp_fish_loc.remove(item)
                        temp_shark = temp[:2]
                    else:
                        br=1
                        break
                if len(temp_smell) >= len(max_smell) and br==0:
                    max_smell = temp_smell[:]
                    max_smell_dir = [i, j, k]

    # 확정된 방향으로 상어 옮기기
    for i in range(3):
        shark = move_shark(shark[0], shark[1], max_smell_dir[i])[:2]

    # 잡아먹힌 물고기 삭제하기

    for target in max_smell:
        for item in fish_loc:
            if item[:2] == target:
                print('지운다', item)
                fish_loc.remove(item)

    # 물고기 복제하기
    for item in fish_save:
        fish_loc.append(item)

    # smell 업데이트
    for i, v in enumerate(smell):
        smell[i][2] += 1

    for i, v in enumerate(max_smell):
        v.append(0)
        smell.append(v)
    result=[]
    for value in smell:
        if value not in result:
            result.append(value)
    smell = result[:]
    return fish_loc, shark, smell

M, S = map(int, input().split())
fish_loc=[]
for i in range(M):
    fish_loc.append(list(map(int, input().split())))
shark = list(map(int, input().split()))

# 물고기 냄새 정의
smell = []

# 메인 함수
for i in range(S):
    
    fish_loc, shark, smell = practice(fish_loc, shark, smell)