[백준 16920번] 확장게임(파이썬)

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

16920번: 확장 게임

bfs를 쓰는 건 알겠는데...

이 문제에서 생각이 잘 안났던 부분은

'Si칸만큼 이동한다'입니다.

보통 bfs쓰면 범위까지 계속 탐색하는데

이동할 수 있는 칸이 정해져있다고??

#백준 16920번 확장게임
from collections import deque
import sys
sys.setrecursionlimit(10**5)

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

N,M,P=map(int,input().split())
S=[0]+list(map(int,input().split()))
gathering=[0]*(P+1)
room=[[0]*M for _ in range(N)]
q=deque()
for i in range(N):
    tmp=input().rstrip()
    for j in range(M):
        if tmp[j]=='.':
            room[i][j]=0
        elif tmp[j]=='#':
            room[i][j]=-1
        else:
            now=int(tmp[j])
            room[i][j]=now
            q.append([i,j])
            gathering[now]+=1


def way(x,y,now,cnt,point):
    global q
    if cnt==point:
        return


    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]
        if nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue
        if room[nx][ny] == -1:
            continue
        if room[nx][ny] > 0:
            continue
        room[nx][ny]=now
        gathering[now]+=1
        q.append([nx,ny])
        way(nx,ny,now,cnt+1,point)



while q:

    x,y=q.popleft()
    now=room[x][y]
    point=S[now]
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]
        if nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue
        if room[nx][ny] == -1:
            continue
        if room[nx][ny] > 0:
            continue
        room[nx][ny]=now
        gathering[now]+=1
        q.append([nx,ny])
        way(nx,ny,now,1,point)

print(*gathering[1:])

저는 처음에 이를

dfs처럼 풀려했습니다.

만약에 3칸 이동할 수 있는데

좌 상 우

이렇게 이동할 수 있으니까요.

그래서 dfs로 이동하면 되겠구나 싶었는데...

이건 재귀함수 에러 이슈도 있었고

오답으로 떴습니다.

 

그러다가 구글링으로 힌트를 얻고 다른 방식으로 구했습니다.

#백준 16920번 확장게임
from collections import deque

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

N,M,P=map(int,input().split())
S=[0]+list(map(int,input().split()))
gathering=[0]*(P+1)
room=[[0]*M for _ in range(N)]
castle=[deque() for _ in range(P+1)]

for i in range(N):
    tmp=input().rstrip()
    for j in range(M):
        if tmp[j]=='.':
            room[i][j]=0
        elif tmp[j]=='#':
            room[i][j]=-1
        else:
            now=int(tmp[j])
            room[i][j]=now
            castle[now].append([i,j])
            gathering[now]+=1

moving=True
while moving:

    moving=False
    for i in range(1,P+1):
        if not castle[i]:
            continue
        q=castle[i]
        for _ in range(S[i]):
            if not q:
                break
            for _ in range(len(q)):

                x, y = q.popleft()
                now = room[x][y]
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if nx < 0 or nx >= N or ny < 0 or ny >= M:
                        continue
                    if room[nx][ny] == -1:
                        continue
                    if room[nx][ny] > 0:
                        continue
                    room[nx][ny] = now
                    gathering[now] += 1
                    q.append([nx, ny])
                    moving=True




print(*gathering[1:])

https://puleugo.tistory.com/85

[백준 16920] 확장 게임 해설 및 풀이 (파이썬)

(참고한 페이지입니다)

제가 심각하게 생각했던 것보다

방법은 간단했습니다.

deque를 플레이어 수 만큼 선언하고

계속 돌려주는 방식이었습니다.

플레이어 하나 하나씩 이동하면서

성을 확장하는 방식이었죠.

아마 제가 처음 고안한 방식으로는

성을 확장할 때

플레이어가 겹치거나

제대로 탐색이 이뤄지지 않은 것 같네요.

 

deque를 다른 방식으로 사용하면서

어떻게 문제를 접근할지 고민하게 해준 문제였습니다.