문제 링크

https://www.hackerrank.com/challenges/queens-attack-2/problem

주의 사항

체스판의 가로 및 세로 (n)과 장애물의 개수 (k) 모두 최대 10의 5승까지 가능하므로
최대 O(NlogN) 복잡도 안에 문제를 풀이해야 한다.

• 처음 접근한 방식은 가로, 세로, 왼쪽 대각선, 오른쪽 대각선을 모두 구한 리스트를 만든 뒤
  각 장애물마다 리스트 내에 존재한다면 그 다음 원소들을 삭제하고자 했다.
  이를 구현하는 과정에서 O(N^2)의 연산이 나와 포기

• 길을 만들어가며 장애물을 만날 때 멈추는 방식이 필요하다는 것을 깨달은 뒤
  진행 가능한 8개의 방향별로 directions 변수를 만든 뒤
  그 방향으로 나아가다가 장애물을 만들면 멈추고 다른 방향으로 진행하도록 함수 설계

문제 풀이

def queensAttack(n, k, r_q, c_q, obstacles):
    if n == 0:
        return 0
    obstacles = set([(i, j) for i,j in obstacles])
    if (r_q, c_q) in obstacles:
        return 0
    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    answer = 0
    for i, j in directions:
        now = (r_q+i, c_q+j)
        while 0 < now[0] <= n and 0 < now[1] <= n and now not in obstacles:
            answer += 1
            now = (now[0]+i, now[1]+j)
    return answer