[Python 3] BOJ 1795 마알

오랜만에 글을 올려본다. 3학년을 보내면서, 전공 수업에 치이고, 과외 수업도 하느라 블로그에 많은 글들을 올리지 못했는데, 이제 휴학을 하기로 마음 먹어서 공부에 대한 내용을 많이 올려보고자 한다. 매일마다 백준 문제를 풀고 있다. (2024년 1월 19일 작성일 기준 208일째) 티어도 플레까지 올렸고.... 더 열심히 해보겠습니다.

 

거두절미하고, 문제 풀이로 들어가자.

---

 

오늘의 문제는 마알 이라는 문제이다.

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

1795번: 마알

 

우선, 문제에 대해서 조금 clarify할 게 있다. 예를 들어, 5-마알이 있다고 하자. 5-마알이 나이트의 이동 방식 (2만큼 한 방향으로 가고, 90도 꺾어서 1만큼 감, 그림 참조)을 꼭 "5번" 할 필요는 없다. 즉, 내가 원한다면, 3번 만 하고 멈춰도 된다. 1번부터 5번까지 나이트의 이동 방식 행한다고 해도, 1회 움직였다라고 정의하겠다라고 생각 하는 것이 이해하기 편할 것이다.

나이트의 이동 반경

 

만약 2번말이 있다고 하자. 모든 빨간 칸도 1회, 초록색 화살표를 통해 따라간 파란 칸도 이동횟수가 1회로 처리된다.

이 문제를 풀기 위해서 각 말에 대해 BFS를 사용했다.

 

코드로 설명하도록 하겠다.

from collections import deque
n,m=map(int,input().split())
data=list(list(input()) for _ in range(n))
horse=[]
dx=[-2,-2,-1,-1,1,1,2,2]
dy=[-1,1,2,-2,-2,2,-1,1]
for i in range(n):
    for j in range(m):
        if data[i][j]!='.':
            horse.append([i,j,data[i][j]])
answer=list(list(0 for _ in range(m)) for _ in range(n))
malcount=list(list(0 for _ in range(m)) for _ in range(n))
for x,y,val in horse:
    q=deque()
    q.append([x,y,val,1])
    visited=list(list(0 for _ in range(m)) for _ in range(n))
    visited[x][y]=1
    malcount[x][y]+=1
    while q:
        x,y,val1,count=q.popleft()
        if int(val1)==0:
            val1=val
            count+=1
        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                q.append([nx,ny,int(val1)-1,count])
                malcount[nx][ny]+=1
                visited[nx][ny]=1
                answer[nx][ny]+=count

number=1e10
for i in range(n):
    for j in range(m):
        if malcount[i][j]==len(horse):
            number=min(number,answer[i][j])

if len(horse)==1:
    print(0)
elif number==1e10:
    print(-1)
else:
    print(number)

 

우선 BFS를 사용하기 위해, Deque을 import 하였다. 이후 각 좌표를 data에 입력받고, '.'이 아닌, 즉 말이 위치해 있는 장소들을 확인하기 위해 2중 for문을 돌면서 말들의 위치와 몇 번 마알인지를 확인하기 위해 horse에 저장하였다. 이후 특정 장소에 모이기 위해서 걸리는 시간을 담는 2차원 리스트인 answer, 말들이 모두 해당 장소에 도착했는지를 확인하기 위한 malcount를 선언하였다. 이후, 모든 horse들에 대하여, deque를 돌면서, 만약 해당 horse가 아직 방문해보지 못한 장소라면, visited를 선언 (이를 통해 해당 말이 이 위치에 다시 오지 않도록 하기 위해), malcount 또한 1 increment (모든 말들이 한 장소로 모여야 하기 때문에 선언함) 한다. 이후 나이트의 이동에 따라서, BFS를 실시한다.

 

만약 malcount에서 말들의 개수만큼 맞춰져 있지 않다면 (즉, 모든 말이 해당 칸에 간다는 것이 아니라면) 이는 모든 말들이 해당 칸에 도착하지 못 한다는 것이므로 제외하고, 이를 만족하는 칸들 중 값이 제일 작은 칸 (제일 적게 이동해도 되는 칸)의 값을 출력한다.  

 

지적, 더 좋은 풀이방법 제안, 질문 및 비판, 칭찬 항상 기다리겠습니다.