백준) 비숍 투어

문제) https://www.acmicpc.net/problem/23885

 

조별로 내준 숙제 중 알고리즘에 너무 매몰 되어 실패한 문제이다.

문제에서 요구하는 조건은 시작점과 도착지점을 주었을 때 시작점에서 도착지점에 갈 수있으면 "YES", 도착하지 못하면 "NO"를 출력 해주면 된다.

 

그래서 단순히 경로 찾기 문제라 생각하여 dfs 방식으로 해당 문제를 풀기 시작

dfs 방식의 코드

import sys
N, M = map(int, sys.stdin.readline().split())
start = list(map(int, sys.stdin.readline().split()))
end = list(map(int, sys.stdin.readline().split()))

dx = [1, 1, -1, -1]
dy = [1, -1, 1, -1]
stack = [(start[0]-1, start[1]-1)]
status = False
visited = []
while stack:
    x, y = stack.pop()
    if [x+1, y+1] == end:
        status = True
        break
    if (x, y) not in visited:
        visited.append((x, y))
        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]

            if 0 <= new_x < N and 0 <= new_y < M:
                stack.append((new_x, new_y))

a = 'YES' if status else 'NO'
print(a)

하지만 결론은 100점 만점의 5점을 받게 되었다.

또한 판을 그린다면 메모리 초과되는 것을 알 수있다. 즉 메모리 제한이 있다.

 

그렇다면 100점을 맞기 위해서 dfs 방식이 아니라면 규칙이 존재 하여 그 규칙으로 프로그램을 다시 짜야 됨을 파악하게 되었다.

 

규칙

체스판에서 비숍은 대각선만 이동이 가능 하다. 즉, 3X3 배열에 비숍의 처음 위치가 (1,1)이라면 (2,2), (3,3) 등으로 갈 수 있으며 (2,1)에 비숍이 있다면 (3,2), (1,2)만 갈 수 있다

이를 통하여 확인 가능 한 건 비숍의 처음에 놓인 위치가 짝수면 짝수칸만, 홀수면 홀수칸만 갈 수 있음을 확인 가능하다.

또한 1X1에서는 이동이 불가능 하다

마지막으로 시작점과 도착점이 같으면 무조건 'YES'이다

 

35점 코드

import sys
N, M = map(int, sys.stdin.readline().split())
start = list(map(int, sys.stdin.readline().split()))
end = list(map(int, sys.stdin.readline().split()))

if start == end:
    print('YES')
elif N == M and N == 1:
    print('NO')
else:
    if sum(start) % 2 == sum(end) % 2:
        print('YES')
    else:
        print('NO')

 

 

 

 

간단하게 출발점과 도착점의 홀짝이 서로 맞다면 이동이 가능하다라는 전제가 되기 위해서는 N, M 둘중 하나는 1보다 커야한다. 

또한 움직일 수 없는 상태에서 출발점과 도착점이 같다면 YES 를 아니라면 NO를 출력해야한다.

이런 식으로 우선순위를 생각하며 코드를 작성 하면 무사히 통과함을 알 수 있다.

 

통과 코드

import sys
N, M = map(int, sys.stdin.readline().split())
start = list(map(int, sys.stdin.readline().split()))
end = list(map(int, sys.stdin.readline().split()))

if N == 1 or M == 1:
    if start == end:
        print("YES")
    else:
        print("NO")

elif start[0] % 2 == start[1] % 2:
    if end[0] % 2 == end[1] % 2:
        print("YES")
    else:
        print("NO")

elif start[0] % 2 != start[1] % 2:
    if end[0] % 2 == end[1] % 2:
        print("NO")
    else:
        print("YES")