[백준] 19236. 청소년상어 - python

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

19236번: 청소년 상어

삼성SW 역량테스트 기출문제

 

---

문제풀이

• 시뮬레이션 + 완전 탐색(dfs)
• 물고기이동
  • 번호가 작은 물고기부터 이동 (1~)
  • 이동가능한 칸
    • 빈칸
    • 다른 물고기가 있는 칸
  • 이동할 수 없는 칸
    • 상어가 있는 칸
    • 공간의 경계를 넘는 칸 (맵을 넘어선 칸)
  • 이동할 수 없으면
    • 45도 반시계 회전하고 이동(8방향 모두 확인)
    • 회전을 해도 이동할 칸이 없으면 이동하지 않음
  • 이동시
    • 다른 물고기가 있으면 서로의 위치를 바꿈
• 물고기 회전
  • 1부터 시작하지만 계산을 쉽게 하기위해 0부터 시작하도록 변경
  • 45도 반시계 방향으로 회전은 현재 회전방향을 나타내는 숫자에 + 1을 해서 나타냄.
  • 이동이 가능한지 확인하기 위해서는 회전을 8방향 모두 해봐야함. ( 반복문을 이용해서 더하는 숫자를 0~7까지로 변경하며 확인)
  • 이 때 숫자가 7을 넘어서면 다시 0부터 시작하도록 설정해야함.
    • (방향숫자 + 회전횟수) % 8

0	1	2	3	4	5	6	7
↑	↖	←	↙	↓	↘	→	↗

 

• 상어 이동
  • 상어가 먹을 수 있는 물고기 번호의 최대값을 구하기이므로 완전탐색을 해야함.
  • 맵이 4*4이고 방향은 변경하지 않고 진행하므로 최대 3개의 경우가 있음
  • 각 경우에 대해서 재귀 호출을 해서 가장 많이 먹은 물고기 번호를 구함.
  • 물고기를 이동시키고 상어를 이동시킨 후 다시 재귀호출로 물고기이동 상어이동을 반복.
  • 이때 물고기 이동 전에 맵을 백업해놓고 호출된 함수로 돌아가기전에 전으로 돌려놔야 함.

---

소스코드 (python)

# 상어이동
def dfs(r,c,d,sum):     #상어 좌표(행,렬), 방향, 먹은 물고기 수
    global ans,m,shark
    #이동 전 맵 복사해놓기
    m_backup = [[[]] * 4 for _ in range(4)]
    for j in range(4):
        for k in range(4):
            m_backup[j][k] = m[j][k][:]
    #물고기 이동
    move()

    if ans < sum :  #가장 많이 먹은 물고기수로 갱신
        ans = sum

    for i in range(1,4):    #맵의 크기가 4*4이므로 상어는 최대 3칸 이동 가능
        #상어의 새로운 좌표 찾기
        snr = r + dir[d][0] * i
        snc = c + dir[d][1] * i
        if snr < 0 or snr >= 4 or snc < 0 or snc >= 4 : break   #범위 벗어나면 집으로
        if m[snr][snc][0] == 0 : continue      #물고기가 없으면 스킵
        #상어이동
        f = m[snr][snc][:]  #물고기 정보 저장
        m[r][c][0] = 0          #지금 좌표는 빈칸으로
        m[snr][snc][0] = -1     #새 좌표로 상어이동
        dfs(snr,snc,m[snr][snc][1],sum + f[0])  #새 좌표로 이동한 후 다시 물고기이동 + 상어이동 재귀로 완전탐색, sum + 물고기로 먹은 물고기수 갱신
        m[r][c][0] = -1         #이동했던것을 취소하기 (다른 경우 확인해보기 위해서)
        m[snr][snc][0] = f[0]

    #호출된 함수로 리턴하기 전에 물고기 이동 취소
    #맵 이전으로 돌려 놓기
    for j in range(4):
        for k in range(4):
            m[j][k] = m_backup[j][k][:]

#물고기 이동
def move():
    for f in range(1, 17):  #작은 번호의 물고기 부터 이동
        isMoved = False     #이동했는지 여부 저장
        for i in range(4):      #맵을 순회하면서 해당번호의 물고기가 아직 이동안했으면 이동시킴
            for j in range(4):
                if not isMoved and m[i][j][0] == f:
                    for k in range(8):  #이동가능한 방향을 탐색하기위한 반복문
                        d = m[i][j][1]  #물고기의 현재방향
                        nd = (d + k) % 8    #새로운 방향, 7을 넘어설때 다시 0으로 돌아가도록 계산
                        ni = i + dir[nd][0] #새로운 좌표 계산
                        nj = j + dir[nd][1]
                        if ni < 0 or ni >= 4 or nj < 0 or nj >= 4: continue     #새로운 좌표가 맵의 바깥이면 스킵
                        if m[ni][nj][0] == -1 : continue    #상어가 있는 곳이면 스킵
                        #아니라면 이동
                        m[i][j][1] = nd     #물고기의 방향을 새방향으로 변경
                        m[ni][nj], m[i][j] = m[i][j], m[ni][nj]     #현재 - 새좌표로 물고기 정보 교환
                        isMoved = True      #이동완료 표시하고 회전반복 빠져나가기
                        break

dir = [[-1,0],[-1,-1],[0,-1],[1,-1],[1,0],[1,1],[0,1],[-1,1]]   #8방향
m = [[[]] * 4 for _ in range(4)]    #4*4 맵을 준비

for i in range(4):
    info = list(map(int,input().split()))
    for j in range(4):
        m[i][j] = [info[j*2],info[j*2+1]-1] #두개씩 끊어서 맵에 배열로 입력하기, 방향숫자를 0부터시작하도록 -1해줌

#상어 : -1, 빈칸 : 0
ans = 0
s = m[0][0][:]     #상어
m[0][0][0] = -1             #처음 상어위치 맵변경
dfs(0,0,s[1],s[0])     #상어좌표, 방향, 먹은 물고기수

print(ans)