# 치킨 배달 비트마스킹 복습 ⭐️몇번째 치킨집이 있는지 &연산 후 연산 결과를 비교할 때 == 1이 아니라 != 0 을 써야하는 이유\ subset & (1<\ 여기서 "최소 거리"만 보고 당연히 집 위치를 기준으로 **BFS 탐색을 한다고 생각**했다. 2. **거리 계산 방식 틀림!!!**\ 거리를 구할 때 현재 위치의 dist에서 +1한 값이 거리가 되는 것이 아니라, 치킨집을 찾으면\ |r1-r2| + |c1-c2| 가 거리가 된다.\ **문제에서 주어진 거리계산 방식으로 각 집에서 각 치킨집까지 거리 구하고, 이 거리의 최솟값이 해당 집의 최종 치킨거리가 된다!!!!!!** 3. 탐색을 진행한다고 쳐도, 다음으로 이동할 좌표를 큐에 넣을 때 난관에 봉착했다.\ (범위, 중복 체크 후) Map값이 0,1,2인지에 따라 이동을 할 것인가 말 것인가? BFS ❌ **구현, Brute Force, 비트마스킹 문제**인 것을 알아차려야한다!!!⭐️\ 어떤 특정 위치 하나를 기준으로 최소거리를 갖는 2의 위치 또는 그 거리를 찾는 것이 아니라,❌\ **여러 점들이 있고**, 각 점에 2까지의 거리는 여러 개가 있을 수 있는데 각 점에서 2까지 **최소 거리를 구해야 한다.**\ 각 점에서 구한 2까지 최소 거리 각각 중에서 최솟값이 최종 정답이 된다. BFS로 접근했을 때 다음으로 이동할 좌표 판단\ \=>결국 0,1,2 모두 다음 이동 좌표로 큐에 넣을 수 있는데 3번의 경우는 큐에 넣기 전에 바로 거리값을 구할 수 있다고 해도, 큐에 넣지 않으면 이동할 수가 없다. 큐에 넣으면 2인 칸(치킨집)을 기준으로 BFS 탐색을 해버리기 때문에 오답이 출력된다!!! 1. Map\[nx]\[ny] == 0 : 이동 가능. 2. Map\[nx]\[ny] == 1 : 이동 가능. 집 위치를 기준으로 BFS를 탐색하지만 그렇다고 Map\[nx]\[ny]가 1인 녿드만 넣는다면 상하좌우가 0으로 둘러쌓여있다면 치킨집(2)을 찾기 위한 탐색을 진행하지 못할 것이다. 3. Map\[nx]\[ny] == 2 : 이동 가능. 하지만 큐에 넣는다면 큐에서 뽑고 이 위치에서 BFS를 시작할 텐데 틀렸다. 집(Map\[x]\[y] == 1)에서 거리를 구하는 탐색을 진행해야한다!\ \=> 다음 노드로 넣기 전에, Map\[nx]\[ny] == 2인지를 검사해서 맞다면 거리계산해서 dist에 넣어준다. 문제를 다시 읽어보면 ② 이 문제에서 요구하는 정답이다.\ ① 각각의 집의 치킨 거리를 구하고, =>**각 집마다 치킨거리(최소거리 치킨집) 구해야한다!**\ \&#xNAN;**=> 집에 대한 반복문 구현 필요!**\ **각 집에서 치킨 거리 구하기⭐️⭐️⭐️⭐️⭐️**\ **1이 M개인 각 부분집합에 대해서 몇 번째 비트가 1인지 알아야한다.⭐️⭐️⭐️⭐️⭐️**\ **M = 2, 현재 부분집합 subset = 011이라면 0,1번째 치킨집을 선택했다는 뜻이므로**\ dist = 1번째 집 \~ 0번째 치킨집 거리, dist = 1번째 집 \~ 1번째 치킨집 거리\ dist를 구해서 최솟값을 선택한다.\ **이러한 dist 구하는 과정을 모든 집에 대해 해줘야한다!⭐️⭐️⭐️⭐️⭐️**\ **M 부분집합 A에서 이렇게 구한 최소값 갖는 dist들을 더해서 치킨거리합 구한다.** ② 이 치킨거리들의 합의 최솟값 : ①에서 구한 치킨거리합의 최솟값을 저장한다! 그래도 잘한 부분\ 비트마스킹을 모든 부분집합과 부분집합 갯수가 M개인 것까지는 잘 구현했다.\ 그리고 M개인 부분집합에 대해 최소거리 치킨집을 찾기 위한 자료구조 dist, dist\_sum잘 생성했다.\ dist = INF(최솟값 구하기 위함), dist\_sum = 0\ dist = Math.min(dist,cur.dist+1)//잘못된 거리 계산. 일단 여기서 중점은 이게 아니다.\ \=>논리적 의미 dist = Math.min(dist, 현재 계산한 dist)✅\ dist\_sum+=dist 2번째 풀었는데 틀린 이유 몇번째 치킨집을 선택했는지 &로 비트연산할 때 비트연산 결과를 != 0 하면 맞고, ==1 하면 틀린 답이 나온다!