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