[5주차_금요일] 맥주 마시면서 걸어가기

[yeongleej]

• 사이트 : 백준(BOJ)
• 문제: 맥주 마시면서 걸어가기
• 번호: 9205

[baexxbin]

🤔 시간복잡도 고려사항

• 편의점 수: n ≤ 100
• 테스트 케이스 수 : t ≤ 50
• O(N^2) 가능

💡 풀이 아이디어

• 첫번째 아이디어 (틀림)

  • 집으로부터 거리가 가까운 순으로 정렬한 후, 순차적으로 거리를 보면서 갈 수 있는지 체크
  • 순차적으로 탐색하는 것이 아닌, 갈 수 있는 모든 경로를 탐색해줘야함!
    • 맨해튼 거리가 가까운 순서대로 방문하는 것이 반드시 최적 경로를 보장하지 않음
    • 연결 가능한 모든 노드를 통해 최종 목적지까지 갈 수 있는지를 판단 → BFS

• BFS

  • 입력 받기
    • 집, 페스티벌 장소 따로 받기
    • Node[] stores : 편의점은 배열로 같이 받기
  • bfs수행
  • 현재 노드랑 도착지점 거리가 1000이내면 바로 도착
  • 아니면 편의점 거쳐보기

    처음에 stores는 편의점만, visited는 집과 도착점도 포함해줬는데 그럼 인덱스가 꼬여서, visited도 깔끔하게 편의점만 체크

• 거리 계산

  • 맨하튼 거리 계한 함수: calDist()
  • 맥주 20개로 50미터씩 갈 수 있으니 한번에 1000미터 이동 가능

[icegosimperson]

🤔 시간복잡도 고려사항

• BFS 시간 복잡도 O(V + E) ->O(n^2) 가능
• 최대 이동 거리 : 1000미터 (맥주 20병 * 50)

💡 풀이 아이디어

• 페스티벌까지 맥주 20병 마시며 도착할 수 있는지 푸는 문제
• 그래프 탐색 : 편의점, 페스티벌 -> 노드 -> 연결 여부를 탐색 -> 현재 위치에서 가장 가까운 노드부터 탐색(최단거리)-> BFS
• 노드 개수 : n+2 (편의점 (n) + 집, 페스티벌)
• Point 클래스 사용하여 x, y좌표를 받음
• Queue 이용해서 다음 방문 가능한 지점(편의점, 페스티벌) 탐색
• distance 함수로 맨하튼 거리 계산하여 방문 가능할 경우 -> "happy"
• 방문 불가능 할 경우 -> "sad"

객체 사용을 자주 습관화 하자..!

[yeongleej]

🤔 시간복잡도 고려사항

• T <= 50
• N <= 100 : 편의점 BFS 탐색 => T * O(N^2) 가능

💡 풀이 아이디어

• BFS 탐색
  • (현재 내 위치, 맥주 개수)의 상태를 큐에 삽입
  • 큐에서 꺼낸 현재 위치에서 페스티벌을 갈 수 있는 지 확인하고 갈 수 있다면 끝
  • 아직 페스티벌을 갈 수 없다면, 편의점들 중에서 현재 가지고 있는 맥주로 갈 수 있는 곳을 탐색후 방문

[Jewan1120]

🤔 시간복잡도 고려사항

• 0 ≤ n ≤ 100 → BFS 가능

💡 풀이 아이디어

• 각 좌표를 입력 받아서 모든 맨해튼 거리를 계산
• 시작 지점으로부터 1000 이하의 맨해튼 거리로 0-1 BFS 실행

[KodaHye]

🤔 시간복잡도 고려사항

• 노드의 수: 2 <= 집 + 편의점 + 락 페스티벌 <= 102
• 간선의 수: 102C2 × 2
• 집에서 락 페스티벌까지 갈 수 있는 최소 경로를 찾는 문제
  • 다익스트라: O(ElogV)
  • E: 간선의 수, V: 노드의 수

💡 풀이 아이디어

• Point p[]: 집, 편의점, 락 페스티벌의 좌표를 저장하는 변수
• ArrayList<Node>[] adj: 주어진 지점에 대해 갈 수 있는 모든 간선 만들기
• dijkstra(0): 0에서 시작해서 페스티벌 지점까지 갈 수 있는지 확인하기

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: BFS
• 시간복잡도: 테스트 케이스 t ≤ 50 , 편의점 갯수 0 ≤ n ≤ 100 모든 지점 간의 거리 계산 시 N * (N-1) = O(N^2) > 50 (100^2) = 50 10000 = 500,000 > 10^5 으로 BFS 풀이가능

💡 풀이 아이디어

• 맥주 총 20병 * 50미터에 한 병씩 맥주마심 = 최대 1000미터
• 꼭 편의점을 들리지 않아도 집 > 페스티벌 거리가 1000미터 이하일 경우 "happy"
• BFS 로 풀이해야하는 이유?
  • 편의점 > 집 > 페스티벌인 경우를 고려할 때 현재 지점에서 페스티벌까지 최단거리인지 너비 탐색이 필요함
• BFS 로 풀이 시 고민한 부분?
  • 전체 탐색 범위의 기준을 뭘로 하는지? 목적지까지의 최단 거리를 찾는 것이 아니라 주어진 거리 조건을 만족하는지 확인하는 것이기 때문에 전체를 탐색할 필요가 없음
  • 주어진 거리가 적합한지 방문 체크, 거리 조건 검사를 통해 인근 너비탐색 진행
  • 어떤 방향 기준으로 탐색하는지? 현재 지점부터 인근 거리까지 얼마나 걸리는지 탐색할 때 기준은 문제마다 다르기 때문에 꼭 방향이 아닐 수 있음 지금 문제의 경우 인근을 탐색하는 기준을 "두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이" 로 알려줌

BFS 를 푸는 방법을 정형화된 공식으로 외워서 공식이 적용되지 않는 문제의 경우 접근 방법을 떠올리기 힘들었어요💦 BFS 알고리즘을 사용하는 목적과 기본개념을 먼저 생각하면 좋았을 것 같아요