[Algorithm 풀이] ROOK

문제는 완전 탐색으로 푸는 문제이다. 처음에 bfs 로 풀릴 줄 알았으나 같은 행, 열에 대한 부분만 탐색해야 하기에 완전 탐색으로 푸는 문제이다.

문제

체스에서 룩이라는 기물은 막혀있지만 않으면 룩의 위치에서 같은 행, 같은 열에 해당하는 칸 중 하나로 한 번 이동할 수 있다. 단, 특정 칸이 막혀있다면 그 칸에서부터 더 나아갈 수는 없다. 만약 룩이 아래 그림과 같이 5행 4열에 존재하고 같은 행열에 기물이 없다면 5행이나 4열에 존재하는 칸 중 어디로든 갈 수 있다. 예를 들어, 5행 2열 혹은 1행 4열로 움직일 수 있다. 차례에 주어진 이동 횟수는 한 번이므로 이동이 완료되었다면 상대방의 차례로 넘어간다.

---

입력

8줄에 걸쳐 8x8 체스판의 상태가 주어진다. 이때 0은 기물이 없는 상태이고, 1은 알랩이의 킹을 의미하고, 2는 상대의 룩을 의미하며 3은 그 외 다른 기물들을 의미한다. (킹은 하나만 존재하며, 상대의 룩은 최대 2개까지 있을 수 있다. 그 외 기물들은 최대 29개까지 있을 수 있다.)

0 3 0 0 0 0 0 0
3 1 0 0 0 0 2 0
0 3 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

출력

1

---

코드

  # 해당 좌표를 기준으로 같은 행 과 열에서 1 있는지 확인
  # 있으면 1과 2 사이에 3이 있는지 확인
  # 없으면 잡을 수 있음 flag = 1 
N = 8
arr = [list(map(int, input().split())) for _ in range(N)]
pos = []
# 룩의 좌표 저장
for i in range(N):
  for j in range(N):
    if arr[i][j] == 2:
      pos.append((i,j))
    else:
      continue

def solution(pos): #1,6
  r = pos[0] #1
  c = pos[1] #6
  flag = 1
  #행 탐색
  if 1 in arr[r]: # 행 #[3, 1, 0, 0, 0, 0, 2, 0]
    index_1 = arr[r].index(1)
    if index_1 < c:
      for i in range(index_1, c):
        if arr[r][i] == 3: #사이에 3이 있으면 끝임
          flag = 0
        else:
          continue
    elif c < index_1:
      for i in range(c,index_1):
        if arr[r][i] == 3: #사이에 3이 있으면 끝임
          flag = 0
        else:
          continue
  else:
    flag = 0
      
  #열 탐색
  for j in range(N):
    if arr[j][c] == 1:
      flag = 1
      index_1 = j
      if j < r: #j = 3
        for k in range(j, r):
          if arr[k][c] == 3:
            flag = 0
          else:
            continue
      elif j > r:
        for k in range(r, j):
          if arr[k][c] == 3:
            flag = 0
          else:
            continue
    
  if flag == 1:
    return 1
  elif flag == 0:
    return 0

if len(pos) == 1:
  print(solution(pos[0])) #룩이 1개 있을때
elif len(pos) == 2:
  sol1 = solution(pos[0]) #룩이 2개 있을 때
  sol2 = solution(pos[1])
  print(sol1 or sol2)

 

⭐️ SOLUTION

1. 우선 구현 문제임으로 차근차근 rook 의 좌표를 기준으로 행 / 열을 탐색한다.
2. flag 를 이용하여 갈 수 있음과 없음을 표시한다.

3. CASE 1 : 같은 행과 열에 킹(1)이 있는 경우
3-1. 킹의 인덱스와 기준, 룩 사이에 3이 있으면 flag = 0
3-2. 없으면 flag = 1

4. CASE 2 : 같은 행과 열에 1이 아예 없는 경우 (헷갈렸던 케이스)
4-1. 행 안에 1이 없으면 무조건 flag = 0으로 만들어줌.
4-2. 열 안에 1이 있는 조건에 들어가면 flag = 1 으로 만들어줌
(열 탐색 할 때 1이 안나오면 행에서 flag =0 지정 한 것이 유지됨)