[2021 카카오 채용연계형 인턴십] Q2. 거리두기 확인하기 (C++, Python, Java)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/72410

 

예상 난이도

S5

 

알고리즘 분류

구현 or BFS/DFS

 

풀이

우선 단순 케이스 분류로 해결하는 풀이를 먼저 보겠습니다. 거리가 2 이하인 두 지점의 배치는 이렇게 3가지의 종류가 있습니다.

 

Case 1과 같은 배치가 나오면 바로 거리두기가 위배되었음을 확인 가능합니다.

 

Case 2와 같은 배치에서는 두 군데의 ? 지점이 모두 파티션인지 확인해야 합니다.

 

Case 3에서는 한 군데의 ? 지점이 파티션인지 확인해야 합니다.

 

각 응시자의 위치에 대해 Case 1, 2, 3번에 대응되는 위치들을 확인하면서 거리두기가 위배된 곳이 있는지 확인하면 됩니다. 여러 위치들을 하나하나 다뤄도 되지만 BFS/DFS에서 사용되는 방향 벡터를 이용하면 구현이 쉬워집니다. 자세한건 코드를 참고해주세요.

 

직접 구현을 하지는 않았지만, 각 응시자의 위치를 시작점으로 두고 BFS 혹은 DFS를 돌려 거리가 2 이내인 곳에 다른 응시자가 있는지 확인하는 풀이도 통과 가능합니다.

 

코드(C++)

 

코드(Python)

 

코드(Java)

 

관련 강의

0x09강 - BFS

0x0A강 - DFS