[Python] 4룩 문제

Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬을 공부하는 도중, 8퀸 문제가 도무지 이해가 안되는 관계로... 4룩 문제로 대체해서 이해해보기로 하였다.

pos = [0] * 4       # 각 열에서 룩의 위치
flag = [False] * 4  # 각 행에 룩을 배치했는지 체크

def put() -> None:
  for i in range(4):
    print(f'{pos[i]:2}', end='')
  print()

# i열 j행
def set(i: int) -> None:
  for j in range(4):
    if not flag[j]: # j행에 룩을 배치하지 않았으면
      pos[i] = j
      if i == 3:
        put()
      else:
        flag[j] = True
        set(i + 1) # 다음 열에 룩을 배치
        flag[j] = False

set(0)

4×4 룩 배치 문제 (백트래킹 설명)

---

1. 4룩 문제란?

• 4×4 체스판에서 4개의 룩을 배치하는 문제
• 룩(Rook)은 같은 행(row) 또는 같은 열(column)에서 다른 룩을 공격할 수 있음
• 따라서, 각 열마다 한 개씩만 배치하면서, 행이 겹치지 않게 배치해야 함

---

2. 4×4 체스판 예제 (백트래킹 과정 포함!)

1. 한 번에 한 열씩(set(i)) 룩을 배치
2. 각 행에 룩이 있는지를 flag[j] 배열로 관리
3. 배치할 곳이 없으면 백트래킹(되돌아가서 다른 행을 시도)

---

🔹 Step 1: 첫 번째 열 (set(0))

• j=0 (0행에 룩 배치)
• pos[0] = 0, flag[0] = True

R . . .    (룩 배치: (0,0))
. . . .
. . . .
. . . .

👉 set(1) 호출 (다음 열로 이동)

---

🔹 Step 2: 두 번째 열 (set(1))

• j=1 (1행에 룩 배치)
• pos[1] = 1, flag[1] = True

R . . .  
. R . .    (룩 배치: (1,1))
. . . .
. . . .

👉 set(2) 호출 (다음 열로 이동)

---

🔹 Step 3: 세 번째 열 (set(2))

• j=2 (2행에 룩 배치)
• pos[2] = 2, flag[2] = True

R . . .  
. R . .  
. . R .    (룩 배치: (2,2))
. . . .

👉 set(3) 호출 (다음 열로 이동)

---

🔹 Step 4: 네 번째 열 (set(3))

• j=3 (3행에 룩 배치)
• pos[3] = 3, flag[3] = True

✅ 모든 룩 배치 완료! 하나의 해결 방법을 찾음.

R . . .  
. R . .  
. . R .  
. . . R    (룩 배치: (3,3))

👉 put() 함수 호출 → 결과 출력
👉 이제 백트래킹을 시작해서 다른 경우의 수도 찾는다!

---

3. 백트래킹 과정 (되돌아가서 다른 경우 탐색)

이제 다른 경우도 탐색해야 하므로 되돌아가서 다른 선택지를 확인해본다.

🔹 Step 4에서 백트래킹

• set(3)에서 룩을 j=3이 아닌 다른 행에 놓을 수 있는지 확인
• j=3 외에는 다른 행에 룩을 놓을 수 없음 → set(3) 종료
• 되돌아가서(백트래킹) set(2)로 복귀

🔹 Step 3에서 백트래킹

• set(2)에서 j=2 대신 다른 행을 시도
• j=3에 룩을 배치 (pos[2] = 3, flag[3] = True)

R . . .  
. R . .  
. . . .    
. . R .    (룩을 (2,2) → (2,3)으로 변경)

👉 다시 set(3) 실행

---

이런 방식으로 모든 경우의 수를 탐색해서 해결 방법을 찾을 수 있다.

---

4. flag[j] = False가 왜 필요할까?

• 백트래킹을 하려면 flag[j] = False가 필수

• 예를 들어, set(3)에서 flag[3] = True였다가 다시 set(2)로 되돌아가면, 이전의 flag[3] = True가 남아 있어서 새로운 탐색을 못 하게 된다.

• set(3)에서 더 이상 배치를 못해서 set(2)에서 행의 위치를 바꾸려고 하는데, 이때 flag[3]가 여전히 True로 남아 있으면 set(2)에서 j=3에 룩을 놓지 못하게 되어, set(2)에서 다른 행을 시도하는 것이 불가능해진다.

• 따라서 set(2)으로 돌아가서 다른 행을 시도하려면, flag[3]를 False로 바꿔줘야 그 행이 다시 사용 가능한 상태가 되어, 새로운 배치를 시도할 수 있게 된다.