[Lv2] 거리두기 확인하기(python)

1. 문제

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

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

 

2. 접근 방법

1) 모든 인원끼리의 맨해튼 거리가 2 이하인지 확인 => 각 인원 끼리의 쌍(nC2)를 구한 후, 각 쌍끼리의 거리가 하나라도 2 이하면 return

 

2) 단, 맨해튼 거리가 2 이하일 지라도 사이에 파티션 ( "X" ) 이 있다면 상관 없음

 

3) 각 인원의 좌표값으로 쌍 만들기 => c++에서 vector< tuple(x,y) > 느낌으로 저장하고 싶어서 고민하느라 오래걸렸는데, python은 그냥 좌표값을 list 형식으로 넣으면 된다!

 

4) 두 응시자 간의 맨해튼 거리에 대해 경우의 수를 나누면 다음과 같다.

    * 거리가 2 초과 -> 거리두기 O

    * 거리가 1 -> 거리두기 X (바로 옆에 앉았다는 의미이므로)

    * 거리가 2 & 두 응시자가 대각선으로 앉은 경우 -> 두 응시자의 대각선에 파티션 2개가 있으면 거리두기 O,아니면 X

                   & 두 응시자가 한 줄로 앉은 경우 -> 두 응시자의 중간에 파티션 1개 있으면 거리두기 O, 아니면 X

 

 

3. 실수했던 부분 & 처음 알았던 부분

1) list에서 특정 값이 있는지 확인하는 법: "value" in array:

 

2) 리스트에 좌표값 넣을 때  []으로 꼭 감싸기!

 

3) 중간 좌표 구할 때, array[ (x1 + x2) / 2 ] 하면 에러남 --> 나눗셈 할 때 형 변환하기!!

4. 코드

from itertools import combinations

def solution(places):
	answer = []
	
	for place in places:
		person = [] #각 응시자의 좌표값
		result = 1 
		for i in range(5):
			for j in range(5):
				if place[i][j] == 'P':
					person.append([i, j])

		#응시자 별 조합 배열 생성
		comb = list(combinations(person,2))

		#응시자 조합 별 거리 구하기 ( 파티션 고려 )
		for pos_pair in comb:
			dist_x = abs(pos_pair[0][0] - pos_pair[1][0]) #두 응시자의 x좌표 거리
			dist_y = abs(pos_pair[0][1] - pos_pair[1][1]) #두 응시자의 y좌표 거리
			
			#거리가 2 초과면 다음 조합으로 넘어감
			if dist_x + dist_y > 2:
				continue
			
			#거리가 1이면 바로 옆에 있는 것이므로 result = 0
			elif dist_x + dist_y  == 1:
				result = 0
				break
					   
			#거리가 2인 경우 중에서 대각선으로 앉은 경우, 2개의 파티션이 없으면 result = 0
			elif dist_x == 1 and dist_y == 1:
				if place[pos_pair[0][0]][pos_pair[1][1]] != 'X' or place[pos_pair[1][0]][pos_pair[0][1]] != 'X':
					result = 0
					break
			#거리가 2인 경우 중에서 일직선으로 앉은 경우, 사이에 1개 파티션이 없으면 result = 0
			else:
				if dist_x == 0 and dist_y == 2 and place[pos_pair[0][0]][int((pos_pair[0][1] + pos_pair[1][1])/2)] != 'X':
					result = 0
					break
					   
				elif dist_x == 2 and dist_y == 0 and place[int((pos_pair[0][0] + pos_pair[1][0])/2)][pos_pair[0][1]] != 'X':
					result = 0
					break					   
		answer.append(result)
	return answer