알고리즘 풀이 백준(BOI) 19237) 어른 상어(Python)

백준(BOI) 19237 - 어른 상어

---

 

 

 

19237번: 어른 상어

 

[문제풀이]

 

 

 상어의 움직임을 시뮬레이션하면서 어른상어(1번 상어)만 남을 때의 카운팅을 출력하는 문제이다. 상어의 움직임 조건이 상당히 복잡

 

하여 이를 구현하는데 조금 애먹었다. 상어의 현재 위치와 방향등을 저장하고 이를 불러오는 방식으로 시뮬레이팅 하였으며 별 다른 특

 

별한 점은 없었다. 

 

주의할 점은 상어의 방향을 정해줄 때 냄새가 없는 공간을 먼저 탐색하고 그러한 공간이 없을 때 다시 자신이 왔던 길로 되돌아가야 한

 

다는 점이다.

 

 

문제에서 주어진 로직은 다음과 같다.

1. 상어가 자신이 있는 자리에 냄새를 남긴다. (냄새는 상어의 번호를 가지며 일정한 시간 뒤 사라진다.)
2. 모든상어가 동시에 이동한다. 상어는 이동 할 때 다음 기준을 따른다. 한 번의 이동은 1초이다.
   2-1. 상어가 바라보는 방향에 대한 우선순위를 참조하여 다음 방향을 결정한다. 다음 방향이 다른 상어의 냄새가 없는 빈 칸이라면 방향 결정.
   2-2. 위 2-1)만족되는 방향이 없으면 (즉, 빈 칸이 없으면) 왔던 방향으로 (자신의 냄새가 있는 칸으로) 돌아간다.
3. 한 칸에 상어가 두 마리 이상 있으면 가장 낮은 번호의 상어를 제외하고는 소멸한다.
4. 위 로직을 계속 반복하면서 1번 상어만 남게 될 때 몇초인지 출력한다. 1000초가 지나면 -1을 출력한다.

 

상어가 "동시에" 이동하며 한 칸에 여러마리의 상어가 들어갈 때 가장 낮은 상어만 남는 것을 구현하기 위해 그리드를 2개 사용하였다.

 

여담이지만 삼성 문제는 시간과 메모리에서 항상 여유가 있는 것 같다.

 

 

---

 

[전체 소스코드]

def makeStateGrid():
    global grid, n
    statearr = [(-1,-1) for _ in range(m)]
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 0:
                statearr[grid[i][j]-1] = (i,j)
    return statearr

def copy(grid2):
    global n, grid
    arr = list()
    for i in range(n):
        for j in range(n):
            if len(grid2[i][j]) >= 1:                
                for num in grid2[i][j]:
                    arr.append(num)
                arr.sort()
                grid[i][j] = arr.pop(0)
                arr.clear()

def move():
    global grid, smellgrid, dirstatarr, dirgrid, n, m
    grid2 = [[[] for _ in range(n)] for _ in range(n)]
    statearr = makeStateGrid()
    for i in range(m):
        nowx, nowy = statearr[i]
        if nowx == -1 or nowy == -1 : continue
        nowdir = dirstatarr[i] - 1
        oper = True
        for j in range(4):
            nextdir = dirgrid[i][nowdir][j] - 1
            dx, dy = directions[nextdir]
            nextx = nowx + dx
            nexty = nowy + dy
            if 0 <= nextx < n and 0 <= nexty < n and len(smellgrid[nextx][nexty])==0:
                grid2[nextx][nexty].append(i+1)
                grid[nowx][nowy] = 0
                dirstatarr[i] = nextdir + 1
                oper = False
                break
        if oper:
            for j in range(4):
                nextdir = dirgrid[i][nowdir][j] - 1
                dx, dy = directions[nextdir]
                nextx = nowx + dx
                nexty = nowy + dy
                if 0 <= nextx < n and 0 <= nexty < n and len(smellgrid[nextx][nexty])>0 and smellgrid[nextx][nexty][0] == i+1:
                    grid2[nextx][nexty].append(i+1)
                    grid[nowx][nowy] = 0
                    dirstatarr[i] = nextdir + 1
                    oper = False
                    break                
                
            
    copy(grid2)

def spread():
    global grid, smellgrid, n, k
    for i in range(n):
        for j in range(n):
            if len(smellgrid[i][j]) > 0 :
                smellgrid[i][j][1] -= 1
            if len(smellgrid[i][j]) > 0 and smellgrid[i][j][1] == 0: smellgrid[i][j].clear()
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 0 :
                smellgrid[i][j] = [grid[i][j], k]

def check():
    global grid, n
    for i in range(n):
        for j in range(n):
            if grid[i][j] > 1: return False    
    return True



n, m, k = map(int,input().split())
grid = [list(map(int,input().split())) for _ in range(n)]
smellgrid = [[[] for _ in range(n)] for _ in range(n)]
dirstatarr = list(map(int, input().split()))
dirgrid = [[]for _ in range(m)]
answer = 0
directions = (-1, 0), (1, 0), (0, -1), (0, 1)
for i in range(m):
    for t in range(4):
        temp = list(map(int,input().split()))
        dirgrid[i].append(temp)
                    
while True:
    if answer >= 1000 : answer = -1; break;
    answer += 1
    spread()
    move()
    if check() : break
    
print(answer)