2020 ICPC Seoul Regional 예선 후기

문제 : 2020 ICPC Seoul Regional 예선

ICPC Seoul Regional 2020 예선 (ProblemSet / Scoreboard) – ACM-ICPC Korea Regional Site

어제는 2020 ICPC Seoul Regional 예선을 쳤다.

작년 ICPC가 끝난 이후로 PS공부를 반쯤 때려치운 상태였는데

한 2-3주 남기고 허겁지겁 공부를 다시 하다 보니 확실히

작년에 비해서 코딩 실력이 떨어진 것이 체감되었다.

설상가상으로 원래 팀원이었던 친구가 코로나 19 때문에

2학기를 휴학하고 군대를 가기로 결정해서 급하게 팀원을 구해 참가하게 되었다.
코로나 때문에 덩달아 교내 대회도 취소되어서 친구 자취방에 모여 대회를 진행했다.

이번에도 당연히 등록 문제가 나올 줄 알고 시작하자마자

문제 제목을 쭉 훑었는데 Registration이란 이름이 안 보여서 좀 당황(?)했다.

---

E번 (Cycle Game)

Solve : he1fire

Code : he1fire

일단 영어 해석도 잘 못하고 한글 문제가 저번 대회 때 쉬웠기 때문에

모두 빠르게 한글 문제를 읽어보다가 팀원이 구현 문제 같다고 넘겨주었다.

문제를 읽어보니 UnionFind를 사용해 Disjoint Set을 합쳐주다가

같은 집합에 들어간 두 수가 입력으로 주어지면 출력하는

간단한 문제라 바로 코딩한 후 제출해서 맞았다.

I번 (Project Teams)

Solve : logeon0725, he1fire

Code : he1fire

나머지 팀원이 각각 L, K번을 보고 있었고

E번을 제출한 후 스코어보드를 보니 대부분 I번을 풀었길래 읽어보니

2명으로 구성된 N개의 팀의 역량 합의 차이가 가장 적게 만드는 것이므로

주어지는 수들을 정렬한 후 앞과 뒤에서 하나씩 수를 뽑아

더한 값의 최소를 출력하면 되는 문제였다.

원래 더 빨리 풀 수 있었는데 N명으로 구성된 2개의 팀으로 잘못 읽어서

코딩을 잘못했고, 팀원이 그 부분을 빨리 알려주어서

그나마 시간을 아낄 수 있었다.

K번 (Road Reconstruction)

Solve : marona, he1fire

Code : he1fire

I번을 푼 이후 팀원이 K번을 가져다주면서

최단경로를 찾는 문제라는 것을 알려주었다.

문제를 읽어보니 도로건설비용이 0,1,2인 행렬이 주어질 때

맨 오른쪽 아래에 최소비용으로 도착해야 하므로

음수 가중치가 없기 때문에 Dijkstra 알고리즘을 사용하면 풀 수 있다.

코딩을 다하고 난 후 제출하기 전에 뭔가 찜찜해

다시 읽어보니 시작 지점이 -1이 아니라는 조건이 없어

Dijkstra를 돌리기 전에 시작 지점이 -1인지 체크하는

조건문을 추가해 제출하니 맞았다.

F번 (Escaping)

Solve : he1fire

Code : he1fire

세문제를 푼 이후에 스코어보드를 확인해 보니

4 솔브 이상을 한 대부분의 팀이 F번이나 L번을 풀어서

두 문제를 나눠 풀기로 했는데 L번이 문자열 문제였기 때문에

쉽게 해결책이 떠오르지 않아 F번을 잡게 되었다.

가장 먼저 문제를 읽고 든 생각은 경찰을 기준으로 BFS를 돌려서 

배열을 채운 후 도둑도 마찬가지로 BFS를 돌려서 도둑이 갈 수 있는 모든 칸이

이미 경찰이 도착할 수 있는 칸이라면 탈출이 불가능한데

주어지는 좌표의 범위가 -10^9 ~ 10^9라 배열을 쓰는 것이

불가능해서 다른 방법을 떠올려야 했다.

결국 이문제에서 1시간 정도를 끙끙대면서 생각했는데

어차피 도둑이 지그재그로 탈출 가능한 경우에는

직진만 해도 탈출이 가능하단 사실을 깨달았고

도둑의 위치를 기준으로 삼아 위, 아래, 왼쪽, 오른쪽에 경찰이 있어

사방이 다 막힌 경우에만 탈출이 불가능하단 사실을 알았다.

이때, 경찰이 어떤 한 방향에서 도둑보다 앞서있더라도

반대쪽 축의 차이가 그보다 크면 체포할 수 없다는 사실을 생각 못해서 틀리고

절댓값을 사용해 다른 축에서의 거리를 확인하는 조건문을 추가해 풀 수 있었다.

---

결과적으로는 4 솔브로 E, F, I, K번을 풀었는데

아직 스코어보드가 공개되진 않았지만 작년과 솔브수는 같은데

훨씬 느리게 풀어서 아마 본선 진출은 못할 것 같다.

특히 F번 문제에서 많이 헤맸는데 좀 더 빨리 풀고 다 같이 L번에 집중했다면

5 솔브도 할 수 있었을 것 같아 아쉬움이 많이 남는다.

이번 대회는 쉬운 문제 중에서 단순 알고리즘 구현 문제가 많이 나와서

어쩌다 보니 나 혼자서 4문제를 다 풀게 되었는데,

확실히 나는 아는 지식 내에서는 잘 풀지만 그 범위가 너무 좁기 때문에

새로운 알고리즘을 공부해야 할 필요성을 좀 많이 느낀 것 같다.