백준 1989 - 체스 (Python)

처음으로 풀어본 제대로 된 그래프 탐색 문제. 여전히 BFS와 DFS는 어렵기만 하다.

​

Function#1 나이트 이동가능 위치 지정

Function#2 나이트 놓기 (multiple knight로 인한 이동 가능위치와 놓는 위치의 간섭이 문제를 망친다)

Function#3 폰 놓기

Function#4 퀸 놓기 (폰을 뛰어넘을 수 없고 나이트도 뛰어넘을 수 없으니 1, 4 만나면 break)

변수선언부(chess에 2차원 배열로 체스판 받기)

Solution:

 

순서가 핵심이다. 어떻게 하면 간섭을 일으키지 않을지를 고민한 결과,

1. 나이트 이동 가능 범위 찾기

2. 나이트 놓기

3. 폰 놓기

4. 퀸 놓기+퀸 이동 가능 범위 파악 의 순서로 놔야 한다고 생각했다.

​

이 순서가 아니라면 반례가 있기 때문이다.

c.e.) 나이트 놓은 곳이 다른 나이트의 이동 가능 범위일 경우, 퀸은 그 곳을 뛰어넘게 됨

c.e.2) 폰 놓은 곳이 나이트 이동 가능 범위일 경우여도 퀸은 그 곳을 뛰어넘게 됨

​