[내일배움캠프 22일차 TIL] 백준 23885 비숍 투어 with python

 백준 23885번 비숍 투어 문제는 다음과 같다

 

비숍은 대각선 방향으로만 움직일 수 있는데

출발점과 도착점이 주어졌을 때 비숍이 출발점에서 도착점에 갈 수 있다면 "YES"를 출력하고

갈 수 없다면 "NO"를 출력하는 문제이다

 

 

---

처음 이 문제를 마주했을때는 냅다 깊이 우선 탐색을 이용해서 풀었는데

문제 조건에 체스판의 크기가 최대 10^9의 제곱이기 때문에

실제로 제출했을 때 메모리 초과라는 결과를 받았다....

 

그래서 열심히 체스판을 그려가며 알아낸 결과

 

색칠이 된 부분끼리 이동할 수 있고 색칠이 안 된 부분끼리 이동할 수 있다

그래서 처음엔 거리를 계산해봤는데 별다른 규칙을 찾지 못했고 

그 다음으로 시도한 방법이 좌표를 비교하는 방법이었다

 

그 결과 출발 위치와 도착위치의 x좌표와 y좌표의 값의 차이가

모두 짝수이거나 모두 홀수인 경우 이동이 가능했다.

 

이를 바탕으로 코드를 작성했다

# 두 좌표의 차이
dx, dy = abs(ed_x - st_x), abs(ed_y - st_y)

if (dx%2 == 0 and dy%2 == 0): # 시작점과 끝점의 차가 모두 짝수인 경우
    print("YES")
elif (dx%2 != 0 and dy%2 != 0): # 시작점과 끝점의 차가 모두 홀수인 경우
    print("YES")
else:
    print("NO")

 

처음에 이렇게 작성한 후에 제출을 했는데 계속 35점만 받았다

어떤 반례가 있길래 통과를 못하는 것인가 생각을 하다가

N 또는 M이 1인 경우가 있다는 것을 깨닫고 코드를 수정했다

 

N 또는 M이 1인 경우에는 시작점과 도착점이 동일한 경우를 제외하고는

두 차가 모두 짝수 혹은 홀수여도 비숍이 이동할 수 없기 때문에 "NO"를 출력해야 한다

 

따라서 아래처럼 코드를 수정한 후에 통과할 수 있었다

# 두 좌표의 차이
dx, dy = abs(ed_x - st_x), abs(ed_y - st_y)

if N==1 or M==1: # 한 줄로 이루어진 체스판
    if dx == dy == 0: # 둘의 좌표가 같아야만 됨
        print("YES")
    else:
        print("NO")
else: # 2X2이상의 체스판
    if (dx%2 == 0 and dy%2 == 0): # 시작점과 끝점의 차가 모두 짝수인 경우
        print("YES")
    elif (dx%2 != 0 and dy%2 != 0): # 시작점과 끝점의 차가 모두 홀수인 경우
        print("YES")
    else:
        print("NO")

 

 

전체 코드는 여기서!

 

---

이 문제에서 반례를 생각해내는데 한 시간이 걸렸다,,,, 반례에 대한 처리는 어려운 부분이 아니었지만 반례를 떠올리기까지 오랜 시간이 걸렸다는 것이 많이 아쉬운 부분이다..! 프로그래머스보다 백준의 커뮤니티? 질문게시판 같은게 많이 활성화 되어있지 않아 혼자 힘으로 생각해내려다보니 더 오래 걸리는 것 같다..! 이 부분은 내가 노력해야지 뭐....