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

구현, 시뮬레이션 

 

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

23290번: 마법사 상어와 복제

문제 요약 및 정리

'''
4x4, 물고기 M 마리, 이동방향 1부터 8까지  ←, ↖, ↑, ↗, →, ↘, ↓, ↙
상어와 물고기 같은 칸 가능, 둘 이상의 물고기 같은 칸 가능

마법 한번 다음과 같은 작업 순서
1. 복제 마법 시전 (5번에서 물고기 복제)
2. 모든 물고기 한 칸 이동
상어가 있는 칸 X, 물고기 냄새가 있는 칸 X, 격자 범위 벗어난 칸 이동 불가
각 물고기는 자신이 가지고 있는 이동방향이 이동할 수 있는 칸을 향할 때 까지 45도 반시계 회전
없으면 이동 X, 방향 제자리 > 이외의 경우 이동
3.상어 연속 3칸 이동(상, 하 좌 우만 가능) 만약 3칸 이동했는데 벗어나면 그 방법은 불가능
이동중 중간에 물고기 모두 제거, 물고기 냄새를 남김
가능한 이동 방법 중 제외되는 물고기가 가장 많은 방법으로 이동
경우가 여러가지면 사전순으로 가장 앞서는 방법 사용

가장 앞서는 방법, 먼저, 방향을 정수로 변환,
상=1 좌=2 하=3 우=4
변환을 모두 마쳤으면, 수를 이어 붙여 정수로 하나 만든다.

두 방법 A와 B가 있고, 각각을 정수로 변환한 값을 a와 b라고 하자.
a < b를 만족하면 A가 B보다 사전 순으로 앞선 것이다.

예를 들어, [상, 하, 좌]를 정수로 변환하면 132가 되고, [하, 우, 하]를 변환하면 343이 된다.
132 < 343이기 때문에, [상, 하, 좌]가 [하, 우, 하]보다 사전 순으로 앞선다.
총 43 = 64가지 방법을 사전 순으로 나열해보면
[상, 상, 상], [상, 상, 좌], [상, 상, 하], [상, 상, 우], [상, 좌, 상],
[상, 좌, 좌], [상, 좌, 하], [상, 좌, 우], [상, 하, 상], ...,
[우, 하, 하], [우, 하, 우], [우, 우, 상], [우, 우, 좌], [우, 우, 하], [우, 우, 우] 이다.

4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
5. 1에서 사용한 복제완료, 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

M, 물고기 수,
S 연습한 수

sx, sy
S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.
'''

풀 때 많이 힘들었던 부분

1. 냄새를 남기고 냄새를 사라지게 하였더니 냄새를 남긴 부분까지 냄새가 감소 

> 먼저 냄새 있는 곳을 +1 해주고 그다음 상어가 먹어서 같은 자리면 -2로 초기화

-2를 계속 뺴주는 것 아님

 

2. 상어 가는 모든 경로 냄새 남기지 않기 

 

3. 방향 1부터 시작인지 인덱스 부터 시작인지 잘 확인하기

 

4. 물고기 개수를 len(배열)로 확인하기, 2개 이상 저장 되어 있을 수도 있으니 바로 arr[][]와 비교하지 않기

 

5.  111, 223 같은 상어 방향 전환을 저장하는 변수는 s 반복문 바로 안에 넣어야 함. 외부로 선언하면 초기화가 안됨 

 

6.

if 만약 최대로 먹은 것 보다 현재 먹은게 많은 경우

   현재 값으로 초기화

 

elif 만약 최대랑 현재 먹은거랑 같다면

  상어 방향 전환이 낮은 값으로 저장하는데 이를 위해 처음부터 111로 초기화 하면 안됨

  왜냐하면 111로 저장해서 주위에 물고기가 모두 없는 경우 계속 111로 진행하여 범위를 벗어나거나 에러가 발생할 수 있음

 

7. 물고기가 같 곳이 없는 경우 

move라는 flag를 사용하여 제자리에 다시 넣음

 

제출 코드 (정답)

def combi(temp):
    global combis
    if len(temp) == 3:
        combis.append(temp[:])
        return

    for j in range(1, 5):
        temp.append(j)
        combi(temp)
        temp.pop()
    return

def DFS(sx, sy, tempEatCnt, dirList, MAP):
    global maxEatCnt
    global ans
    if len(dirList) == 3:
        temp = (dirList[0] + 1) * 100 + (dirList[1] + 1) * 10 + dirList[2] + 1
        if maxEatCnt < tempEatCnt:
            maxEatCnt = tempEatCnt
            ans = temp
        elif maxEatCnt == tempEatCnt:
            ans = min(ans, temp)
        return

    #4방향 가야함
    tempArr = [i[:] for i in MAP]
    for d in range(4):
        nx, ny = sx + sdx[d], sy + sdy[d]
        if nx < 0 or nx >= 4 or ny < 0 or ny >= 4:
            continue
        if len(tempArr[nx][ny]) > 0:
            tempEatCnt += len(tempArr[nx][ny])
            tempArr[nx][ny] = []
            
        dirList.append(d)
        DFS(nx, ny, tempEatCnt, dirList, tempArr)
        tempArr = [i[:] for i in MAP]
        tempEatCnt -= len(tempArr[nx][ny])
        dirList.pop()


M, S = map(int, input().split())
#     ←, ↖,   ↑,  ↗, →, ↘, ↓, ↙
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
sdx = [-1, 0, 1, 0]
sdy = [0, -1, 0, 1]
smell = [[0]*4 for i in range(4)]
arr = [[[] for i in range(4)] for _ in range(4)]

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

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

# 방향 조합 3개 찾음
combis = []

# 물고기 한 칸 이동
for _ in range(S):
    ans = 999
    maxEatCnt = 0
    pastArr = [i[:] for i in arr]
    tempArr = [[[] for i in range(4)] for _ in range(4)]
    #물고기 이동
    for i in range(4):
        for j in range(4):
            if len(arr[i][j]) > 0:
                for d in arr[i][j]:
                    d = d-1
                    for _ in range(8):
                        move = False
                        nx, ny = i + dx[d], j + dy[d]
                        if nx < 0 or nx >= 4 or ny < 0 or ny >= 4 or (nx == sx and ny == sy):
                            d = (d - 1 + 8) % 8
                            continue
                        # 물고기 냄새 있는 칸
                        if smell[nx][ny] < 0:
                            d = (d - 1 + 8) % 8
                            continue
                        else:
                            tempArr[nx][ny].append(d+1)
                            move = True
                            break
                    if not move:
                        tempArr[i][j].append(d + 1)

    arr = [i[:] for i in tempArr]

    # 상어 연속 3칸 이동
    DFS(sx, sy, 0, [], arr)
    if ans == 999:
        ans = 111

    # 두 번 전 연습에서 생긴 물고기의 냄새 1 제거.
    # 물고기에만 영향 미치니 나중에 더함
    for i in range(4):
        for j in range(4):
            if smell[i][j] < 0:
                smell[i][j] += 1

    dirList = [ans//100, (ans%100)//10, ans%10]
    nx, ny = sx, sy
    for d in dirList:
        nx, ny = nx + sdx[d-1], ny + sdy[d-1]
        if len(arr[nx][ny]) > 0:
            smell[nx][ny] = -2
        arr[nx][ny] = []
    sx, sy = nx, ny

    # 물고기 복사
    for i in range(4):
        for j in range(4):
            if len(pastArr[i][j]) > 0:
                for num in pastArr[i][j]:
                    arr[i][j].append(num)
fishCnt = 0
for i in range(4):
    for j in range(4):
        fishCnt += len(arr[i][j])

print(fishCnt)

 

 

후기

와 골드 1 문제네요... 어마어마한 문제였습니다. 정말 너무 어려웠지만 맵에 변화가 잘 보여서 디버그에서 만큼은 큰 어려움이 없었습니다. 

그리고 처음에 중복순열 4x4x4 의 경우를 배열로 만들어서 풀까 생각하고 combi라는 배열을 만들었는데 이렇게 하면 뭔가 에러가 발생할 것 같아서 DFS로 풀었습니다. 

visited를 만들 수 없어서 시간초과 나면 어떡하나 했는데 4x4 라서 그런지 수월하게 통과되었습니다. 

 

그런데 물고기가 갈곳이 없는 경우 제자리에 넣어야 하는데 이 경우를 예제 3번까지도로 찾지 못해 애를 많이 먹었습니다.

 

그래서 저는

 

5 4
4 3 5
1 3 5
2 4 2
2 1 6
3 4 4
4 2

 

정답 26

 

위 예제를 돌려서 정답을 저와 비슷하게 짠 코드를 디버그 해가며 제 문제점을 찾았습니다. 

아마 위 코드까지 맞는다면 무난히 통과할 것입니다.