스터디) 백준 16509:장군 Python 상세 풀이

https://youtu.be/7C9RgOcvkvo?si=XSCKpzmzEpYP8TI9&t=2113

이 BFS 강의를 듣지않고 글을 읽으면 이해가 안갑니다.

초기 세팅

1. 가로,세로,방문여부 리스트
2. 상과 왕의 x,y좌표 지정
3. 이동 횟수 초기값 지정 (count=1)
4.bfs에서 각각 3번 움직일 dx dy 생성
(bfs의 4~8번  설명에서 왜 이렇게 했나 알 수 있음)
5.상의 x,y좌표로 start 리스트 생성
6.bfs에 dx,dy와 start, visited(방문 여부 리스트),count를 넣어주고 bfs실행

#세로,가로
n=10
m=9

#방문여부
visited=[[False]*m for _ in range(n)]

#상,왕의 x,y
sangx,sangy=map(int,input().split())
kingx,kingy=map(int,input().split())

#횟수
count=1

#상좌,상우,하좌,하우,좌상,좌하,우상,우하
dx=[[-1,-1,-1], [-1,-1,-1], [1,1,1], [1,1,1], [0,-1,-1], [0,1,1], [0,-1,-1], [0,1,1]]
dy=[[0,-1,-1], [0,1,1], [0,-1,-1], [0,1,1], [-1,-1,-1], [-1,-1,-1], [1,1,1], [1,1,1]]

#bfs 시작 지점
start=[sangx,sangy]
print(bfs(dx,dy,start,visited,count))

bfs 구현.

 

def bfs(dx,dy,start,visited,count):
    q =deque([[start[0],start[1],count]])
    visited[start[0]][start[1]]=True
    while q:
        v= q.popleft()
        # dx,dy 횟수만큼 빙빙돌아
        for i in range(8):
            block=False
            x=v[0]
            y=v[1]
            # print(x,y)
            for j in range(3):
                # print(i,j,dx[i][j])
                x=x+dx[i][j]
                y=y+dy[i][j]
                if x==kingx and y==kingy and j !=2:
                    block=True
            if block==True:
                continue
                
            if x>=0 and x<10 and y>=0 and y<9 and visited[x][y]==False:
                if x==kingx and y==kingy:
                    return v[2]
                else:
                    q.append([x,y,v[2]+1])
                    visited[x][y]=True

    return -1

 

1.bfs 들어간 후 

q =deque([[start[0],start[1],count]])

으로 
이차원 리스트안에 start[0](상의 x좌표) start[1](상의 y좌표), count(이동횟수) 넣어줌

 

 

2.

visited[start[0]][start[1]]=True

으로 상의 좌표 방문 처리

3.q가 빌때까지(while q). 제일 먼저 들어온 애를 pop하고 변수에 저장

v= q.popleft()

v에는 상의 x,y좌표와 카운트가 인덱스 0,1,2번에 들어있음.

 

 

 

4.pop한 친구를 움직여줄 dx,dy횟수인 8번만큼 for문 생성

for i in range(8):

 

5.block변수를 만들어줌. 다른 장기말이랑 겹치는 여부를 파악해줄 친구임. 

 block=False​

 

6.상의 x,y좌표를 각각 v에서 가져와서 x,y에 넣음

x=v[0]
y=v[1]

 

7. 

for j in range(3):​

 

을 해서
장기말이 dx,dy를 따라 한칸씩 3번 움직이는것을 표현해줌
왜 이렇게하냐면 움직이는 동선에 다른 장기말이랑 겹치는지를 정확히 확인하기 위함. 

x=x+dx[i][j]
y=y+dy[i][j]​

 

 

각각의 움직임에 다른 장기말(여기선 왕 장기말) 이랑 겹치는지 확인.

if x==kingx and y==kingy and j !=2:
	block=True​

 

8.
for문을 나와서 겹쳐서 block이 True가 됐으면 continue로 다음 dxdy로 이동해줌.

  if block==True:
                continue​

*** 4~8 과정으로 예제 3번에서 처음 움직일 때 오른쪽 아래로 움직일때 
왕이랑 겹치는 걸 알 수 있음 ***

 

9. 움직인 후의 좌표가 이미 방문했거나,범위 밖을 벗어나는지 확인.

if visited[x][y]==False and x>=0 and x<10 and y>=0 and y<9:​

 

10. 만약 움직인 값이 킹의 위치와 같으면 그동안의 반복 횟수(v[2],3번에 처음에 넣어줬던 count)리턴

if x==kingx and y==kingy:
                   return v[2]​

 

11.아니라면 q에 그 좌표를 append하고,count(v[2])를 1 올려주고 방문처리. 

else:
                    q.append([x,y,v[2]+1])
                    visited[x][y]=True

 

12. while q 반복문동안 결과를 못냈으면 -1 리턴

 return -1​

 

끗

count(v[2])는 큐에 넣을때 그 친구의 카운트를 같이 넣어줬다는걸 알 수 있습니다.