[BOJ]연세대학교 미래캠퍼스 슬기로운 코딩생활 Open Contest

정말 오랜만에 포스팅하는 것 같다. 군대를 전역하고 나온 후 이런저런 일 때문에 블로그에 신경 쓸 겨를이 없었던 것 같다. 그럼에도 중간에 Java JSP 웹프로그래밍 공부를 하는등 나름대로 시간을 보내고 있었다. 오랫동안 알고리즘 문제를 안풀어서 감이 많이 떨어졌다. 하지만 새로운 목표가 생겼다고 쓰고 싶다. 금년 9월에 시작하는 AI Tech 4기에 지원해볼려고 한다. 미리 준비겸으로 pre-course를 듣고 있고, 그 외에도 머신러닝, 딥러닝 공부를 하고 있다. 2차 시험이 코테인만큼 알고리즘도 더 이상 게으르게 미룰 수 없다. 오랜만에 백준을 들어간 후 마침 대회가 개최된 것을 보았다. 시간이 1시간 정도 지났길래 듣던 강좌를 내팽겨치고 바로 달려들었다. 결과는 대패였다.....5문제 중 2솔에 그쳤다. 심지어 두 문제는 완전히 거져주는 문제였다. C, D는 풀긴 했지만 시간초과로 틀렸다. 허탈한 마음에 대회가 끝난 후 계속 곱씹어보며 어느 부분에서 틀렸는지 확인해보았다. 결국에 한 문제 빼고 전부 풀기는 했지만, 시간이 오래걸렸다는 점에서 갈 길이 먼 것 같다. 먼저 A, B문제는 너무 간단하여서 따로 적지는 않겠다. 틀렸던 C, D 문제를 적어볼까 한다.

연속XOR

문제

준원이는 다음과 같이 A에서 B까지의 자연수들을 나열했다.

 A,A+1,A+2,…,B−2,B−1,B

이 수들에 모두 비트 XOR을 취한 값을 구하라.

입력

두 자연수 A, B가 공백을 사이에 두고 주어진다.

출력

 A이상 B 이하인 모든 자연수들을 XOR한 값을 구하여라.

생전 처음으로 비트 XOR 문제 유형을 마주한 나에게는 입이 떡 벌어질 문제였다. 범위가 10^18인만큼 O(n)마저도 용납하지 않는 무시무시한 문제였다. 결국 인터넷의 힘을 빌리게 되었고, XOR문제에서 황금 같은 공식을 발견하게 되었다. 어렵게 적어들 놔서 뭐라고 하는지 이해하는데 시간이 상당히 걸렸지만, 이 문제를 푸는데 알아야 하는 부분은 

1. 어떤 숫자를 4로 나눴을 때, 0이 남으면 XOR 값은 n, 1면 1, 2는 n+1, 3은 0이다

2. L과 R사이의 값들을 XOR해준 값의 합은 L-1까지 XOR해준 값 ^ R까지 XOR해준 값이다.

코드로 한번 알아보자

def XOR(a):
    if a % 4 == 0:
        return a
    elif a % 4 == 1:
        return 1
    elif a % 4== 2:
        return a+1
    else:
        return 0
a, b = map(int ,input().split())
print(XOR(a-1)^XOR(b))

먼저 XOR을 해준 값을 더한 값을 구해주는 함수를 만들어주자. 무슨 값이 되었든, 4로 나눴을 때 남는 값에 따라 그 값은 정해져 있다. 그 다음 a, b가 주어졌기 떄문에, a-1을 XOR해준 값의 합과 b까지 XOR해준 값을 더해준 값을 XOR해주면 정답이 된다.

특징만 알면 풀 수 있는 문제였기에 더욱 허무했다.

다음은 D문제이다

문제

시루는 부모님과 함께 백화점에 갔다. 부모님은 쇼핑할 것이 많기 때문에 여러 곳을 돌아다녀야 하고, 시루는 부모님과 함께 걸어다니는 것이 너무 힘들어서 의자에 앉아서 쉬려고 한다.

백화점은 세로 길이가 N$N$, 가로 길이가 M$M$인 격자 형태이고, 상하좌우로 인접한 칸으로 이동할 때마다 1 만큼의 체력을 소모한다. 시루는 현재 위치에서 출발해 백화점 곳곳에 있는 의자 중 하나를 찾아가서 앉으려고 한다. 시루는 백화점 밖으로 나가면 부모님께 혼나기 때문에 백화점 밖으로 나갈 수 없다.

백화점에는 건물을 지탱하기 위한 기둥과 옷을 전시하기 위한 마네킹이 있다. 시루는 기둥이 있는 칸으로 이동하지 못하고, 마네킹을 무서워하기 때문에 마네킹과 거리가 K$K$ 이하인 칸은 사용하지 않으려고 한다. 이때 두 칸 (rx,cx),(ry,cy)$(r_x, c_x), (r_y, c_y)$의 거리는 |rx−ry|+|cx−cy|$\vert r_x-r_y \vert + \vert c_x-c_y \vert$이다. 단, 시루가 출발할 때는 부모님과 함께 있기 때문에, 출발 지점과 마네킹과의 거리가 K$K$ 이하가 되어도 출발할 수 있다.

시루는 다리가 너무 아프기 때문에 체력 소모를 최소화하면서 의자까지 찾아가려고 한다. 시루가 소모하는 체력의 최솟값을 구해보자.

입력

첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 N,M,K$N, M, K$가 공백으로 구분되어 주어진다. (1≤N,M≤2000$1 \leq N,M \leq 2\,000$, 0≤K≤4000$0 \leq K \leq 4\,000$)

둘째 줄부터 N$N$개의 줄에 각각 M$M$개씩 위에서부터 차례로 백화점의 상태가 주어진다. 아무것도 없는 칸은 0, 기둥이 있는 칸은 1, 의자가 있는 칸은 2, 마네킹이 있는 칸은 3, 시루의 시작 위치는 4로 주어진다. 시루의 시작 위치는 정확히 한 번 주어지고, 해당 위치에 기둥, 의자, 마네킹이 존재하지 않는다.

출력

시루가 의자를 찾아갈 수 있다면 시루가 소모하는 체력의 최솟값을 출력한다.

만약 의자를 찾아갈 수 없다면 -1을 출력한다.

한 눈에 봐도 BFS 최단경로 문제인것을 알 수 있었다. 나름대로 그래프에 강점을 가지고 있다고 생각했기에 호기롭게 도전하였다. 계속 돌려봐도 틀렸다는 값이 나와서, 시간이 지나고 나서야 시간초과가 되었다. 그 당시 코드는 모든 마네킹들의 좌표를 리스트에 담아둔 후, 이동할려고 할 때 각 nx, ny에 대하여 모든 좌표들을 대조해본 후 거리를 계산하였다. 범위를 보면 시간초과가 당연히 나올만한 코드였다. 결국 그래프를 한번 탐색하여 마네킹들의 좌표들을 deque에 저장한 후, 다른 리스트를 생성하여 마네킹으로부터의 거리를 담는 리스트를 하나 만들었다. 그 다음 nx, ny를 인덱스로 가지는 값이 k보다 크면 continue하는 식으로 풀었다.

del input
from collections import deque
n, m, k = map(int, input().split())
depart = []
for _ in range(n):
    depart.append(list(map(int, input().split())))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q = deque()
visited = [[False for _ in range(m)]for _ in range(n)]
maneking = []
for i in range(n):
    for j in range(m):
        if depart[i][j] == 4:
            q.append([i, j, 0])
        elif depart[i][j] == 3:
            maneking.append([i, j])
flag = False
if n == 1 and m == 1:
    print(-1)
else:
    while q:
        x, y, cnt = q.popleft()
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny <0 or ny >= m:
                  continue
            if visited[nx][ny] or depart[nx][ny] == 1:
                continue
            blocked = False
            for mk in maneking:
                if abs(nx-mk[0]) + abs(ny-mk[1]) <= k:
                    blocked = True
                    break
            if not blocked:
                if depart[nx][ny] == 2:
                    flag = True
                    print(cnt+1)
                    break
                    q.append([nx, ny, cnt+1])
            if flag:
                break
    if not flag:
        print(-1)

느낀점

오랜만의 알고리즘이라 떨리기도 하고 두렵기도 했다. 1년 넘게 지속해온 것이 몇 달 쉬었다고 이 정도로 무너질 줄은 몰랐다. 그럼에도 다시 감 잡는데 오래 걸릴거라고는 생각하지 않는다. 하루하루 쌓아간다는 생각으로 AI TECH 4기 준비 열심히 해봐야겠다!