[프로그래머스] 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기 (파이썬) 문제 및 풀이

문제) 프로그래머스 - 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기

-> https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

 

 

2칸내에 인접한 응시자 있는지, 존재할 경우 파티션 또는 테이블이 있는지 탐색하며 거리두기 여부를 확인한다. 5x5 모양의 대기실 5곳을 1칸당 12번씩 완전탐색하므로 연산수는 대략 5*5*5*12 = 7500이므로 완전탐색을 이용하기에 적합하다.

 

거리두기가 실패할 수 있는 경우를 관찰해보자.

 

1. 응시자가 1칸내로 인접한 경우

1칸 인접

1칸내로 인접한 경우는 파티션의 유뮤와 관계없이 거리두기가 실패하므로 상하좌우 1칸을 탐색하며 확인할 수 있다.

 

 

2. 응시자가 2칸 거리에 있을 경우(대각선X)

2칸 인접(대각선x)

2칸 거리에 일직선 방향으로 응시자가 있을 경우, 응시자와 응시자 사이의 칸(그림에서 별이 들어간 칸)에 파티션의 유무에 따라 거리두기 성공 여부가 갈린다. 

 

 

3. 응시자가 2칸 거리에 있을 경우(대각선O)

2칸 인접(대각선o)

2칸 거리에 일직선 방향으로 응시자가 있을 경우, 응시자와 응시자 간에 2칸 거리로 지날 수 있는 경로 칸(그림에서 별이 들어간 칸) 탐색한다. 이 칸에 둘다 파티션이 있어야 거리두기가 성공이므로 확인해주면 된다.

 

 

 

 

파이썬 소스 코드)