[백준] 구현 코멘트 모음

⭕️ 14503번 : 로봇 청소기 (골드5)

• 문제 유형 : implement, simulation
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 0은 북쪽, 1은 동쪽, 2는 남쪽, 3은 서쪽이기 때문에 왼쪽으로 방향을 돌리고 한 칸을 이동하는 과정을 현재 방향을 나타내는 인덱스에서 1을 빼고 4를 더한 뒤 4로 나눈 나머지를 구하는 방식으로 구현
- 만약 4방향을 모두 둘러 봤을 때 이동할 곳이 없으면 벽이 아닌한 후진하여 이동하는데 이 경우 청소 구역 수를 증가시키지 않음
- 더 이상 이동이 불가하면 총 청소 구역 수를 출력

 

⭕️ 16236번 : 아기 상어 (골드3)

• 문제 유형 : graph, bfs, implement, simulation
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 상어가 먹을 수 있는 물고기들을 선택할 때 가장 가까운 거리에 위치한 물고기 중 선택해야하기 때문에 bfs를 이용
- 거리가 같은 물고기일 경우 가장 왼쪽에 위치한 물고기, 왼쪽 거리도 같다면 가작 위쪽에 위치한 물고기를 선택해야하기 때문에 이에 맞게 우선순위큐의 compare 조건을 지정
- 거리 1당 시간이 1씩 걸리기 때문에 선택한 물고기로 이동할 때마다 떨어진 거리(물고기까지의 bfs시행 횟수)만큼 더하여 총 이동 시간을 구한다

 

⭕️ 9328번 : 벽 부수고 이동하기 4 (골드2)

• 문제 유형 : implementation, graph, dfs, bfs
• 시간 복잡도 : O(nmk)
• 풀이 방식 :

- 벽을 하나 지우고 이동 할 수 있는 칸 수를 각 벽마다 구해야하기 때문에 dfs, bfs 탐색 둘 다 가능
- 모든 벽마다 bfs 탐색을 하면 O((nm)^2)이 되기 때문에 상당한 시간이 걸림
- 시간을 줄이기위해 벽으로 막히지 않고 연결된 길들의 개수를 세서 하나의 그룹으로 모두 묶음 (Node 2차원 배열을 만든 뒤 탐색을 시작한 노드를 기준으로 연결된 모든 노드에 시작 노드를 저장하고 시작 노드의 이동 가능 칸수를 늘림 -> 그룹화)
-벽을 지우고 4방향으로 벽이 아닌 길이 존재한다면 미리 구해둔 그룹의 개수를 바로 더함 (방문한 길의 Node 2차원 배열에 들어있는 노드을 확인해 이동 가능 칸 수를 바로 구함)
- 단순하게 4방향에서 더하면 그룹이 중복 되어 세질 수 있기 때문에 리스트에 방문한 그룹을 저장해두고 만약 인접한 그룹이 리스트 안에 있는 그룹(이미 방문한 그룹)일 경우 더하지 않고 넘어감
- 벽을 지우고 이동 할 수 있는 칸 수를 따로 2차원 배열(그래프)에 저장하고 출력

 

⭕️ 16234번 : 인구 이동 (골드5)

• 문제 유형 : graphs, bfs, implementation, simulation
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 그래프 내의 노드들 중 방문하지 않은 노드에서 bfs 탐색
- 현재 노드에서 4방향 탐색을 진행하여 인접한 노드와의 인구 격차가 L 이상 R 이하이면 해당 노드를 bfs queue와 연합 국가를 저장하는 queue에 넣고 인구값을 sum 변수에 더하고 연합 수를 의미하는 count 변수를 1 늘림
- 하나의 연합을 모두 탐색 했다면 모든 연합 국가의 인구수를 총 인구수 / 연합 국가 수로 바꿈
- 방문하지 않은 노드가 없을 때까지 bfs 탐색
- 인구 이동이 일어나지 않을 때까지 위의 과정을 반복

 

⭕️ 17135번 : 캐슬 디펜스 (골드3)

• 문제 유형 : graph, implementation, simulation, bruteforce
• 시간 복잡도 : O(mC3*nm^2)
• 풀이 방식 :

- m개의 열 중 궁수 자리 3개를 고르는 모든 경우에서 적을 제거 해봐야하기 때문에 벡트레킹을 이용해서 궁수의 자리를 지정
- *첫 풀이에서는 모든 적을 아래로 한 칸씩 이동시켰지만, 역으로 궁수 행을 위로 이동시키면 시간을 줄일 수 있음
- 궁수 행의 첫 위치는 r이며 궁수의 위치가 1까지 가게 되면 반복이 종료 됨(0이면 어차피 쏠 적군이 존재하지 않음)
- 궁수 행 이동 전 각 궁수 위치부터 (위, 오른쪽, 왼쪽)방향으로만 bfs탐색(각 반복마다 q의 사이즈를 체크하고 사이즈만큼 한 번에 탐색 -> 떨어진 거리가 같은 노드들을 한 사이클에 함께 탐색하기 위함)을 진행
- 가장 가까운 적군이 존재하는 노드들 중 가장 왼쪽에 있는 노드를 선택하여 궁수 3명의 타겟을 저장하는 배열에 해당 궁수 인덱스에 저장
- 3명의 궁수가 타겟을 정하게 되면 중복되지 않게 제거되는 적의 수를 카운팅(중복 사격이 가능하기 때문에 bfs탐색에서 적군을 발견하자마자 제거가 아닌 따로 배열에 저장 후 한 번에 처리해야 함)
- 궁수를 배치하는 모든 경우에서 가장 많이 제거한 적군의 수를 출력

 

❌ 14502번 : 연구소 (골드4)

• 문제 유형 : graphs, bfs, dfs, implementation, simulation, bruteforce
• 시간 복잡도 : O((nm)^3)
• 풀이 방식 :

- 바이러스를 인접한 4방향으로 계속해서 퍼트린 후 안전 영역을 구하면 되기 때문에 dfs, bfs 모두 가능
- 벡트레킹을 이용해서 벽 3개를 세울 수 있는 모든 경우에서 바이러스를 시작점으로 bfs 탐색을 진행
- 벽 3개가 세워진 각 경우마다 시뮬레이션을 각각 진행해야 되기 때문에 연구소 지도를 복사해서 사용
- 바이러스가 퍼질때마다 안전 영역의 크기를 줄이면서 가장 큰 안전 영역의 크기를 구함

 

❌  17141번 : 연구소 2 (골드4)

• 문제 유형 : graphs, bfs, implementation, simulation, bruteforce
• 시간 복잡도 : O(10Cm∗n^2*M)
• 풀이 방식 :

- 바이러스를 놓을 수 있는 위치를 리스트에 저장
- 바이러스는 1개부터 m개 모두 놓기까지 모든 경우의 수가 가능하며 각 경우마다 벡트레킹을 이용해서 바이러스를 나열하고 모든 바이러스를 놓았으면 bfs 탐색을 진행하여 바이러스를 퍼트림(bfs 탐색은 그래프의 복사본에서 진행)
- bfs 탐색의 한 사이클은 큐의 사이즈 크기만큼 진행되며(각 시간마다 모든 바이러스의 퍼짐), 사이클마다 큐의 사이즈를 더하여 바이러스가 퍼질 수 있는 구역의 수와 같으면(바이러스가 벽을 제외한 모든 곳에 퍼질 수 있으면) 현재까지 구한 최소 시간과 비교
- *연구소(14502번)을 푼지 오래되서 각 bfs 탐색마다 그래프를 복사해서 따로 사용해야되는 것을 잊음

 

⭕️ 2573번 : 말이 되고픈 원숭이 (골드3)

• 문제 유형 : implementation, graph, dfs, bfs
• 시간 복잡도 : O(nm)
• 1풀이 방식 :

- 시작 지점으로부터 목표 지점까지의 최소 거리를 구하는 문제이기 때문에 기존의 bfs 풀이방식을 이용
- 원숭이의 이동 방법은 단순 4방향 탐색을 통한 1칸 이동과 8가지의 말 형태 이동 2가지
- 말 이동을 사용했을 때보다 단순 1칸 이동을 했을 때 더 빨리 이동하는 경우가 있을 수 있기 때문에 말 이동 사용 횟수별 방문 체크를 따로 해줘야함 (3차원 visit배열 이용)
- 먼저 기존의 4방향 탐색을 하고, 현재 원숭이의 말 이동 횟수가 남아있다면 8방향 탐색또한 진행 (말 이동은 중간에 벽이 있어도 상관 없음)

 

⭕️ 19238번 : 스타트 택시 (골드3)

• 문제 유형 : implementation, graph, bfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 손님과 목적지로 가는 최소 경로를 찾아야하기 때문에 bfs 탐색을 이용
- 택시에 손님이 타고 있지 않으면 우선순위 큐와 큐의  조건에 맞는 가장 가까운 손님을 찾아가 택시에 태움 (현재 위치에 손님이 서 있을 수 있기 때문에 현재 위치에서 손님 확인 또한 해야함)
- 떨어진 거리가 똑같은 물고기들만 우선순위 큐에 들어가야하기 때문에 현재 큐의 크기만큼만 빼내어 탐색
- 손님이 타고 있는 상태면 4방향 bfs 탐색을하여 목적지까지 찾아간 후 소모된 연료의 2배만큼 더함
- 모든 손님을 택시에 태웠으면 남은 연료량을 출력

 

⭕️ 13460번 : 구슬 탈출 2 (골드1)

• 문제 유형 : implementation, graph, bfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 빨간 구슬이 구멍으로 탈출하는 최소 횟수를 찾아야하기 때문에 빨간 구슬, 파란 구슬의 좌표 정보를 담고 있는 Node의 bfs 탐색을 이용
- 일반적인 4방향 탐색과는 달리 보드를 기울여 이동하기 때문에 구슬은 기울어진 방향으로 갈 수 있는 위치까지 이동
- 만약 빨간 구슬과 파란 구슬이 일직선 상에 위치할 경우 이동 방향으로 앞선 구슬이 먼저 움직여야하기 때문에 4방향 모두에서 앞의 조건을 확인해가며 두 구슬을 이동
- 파란색 구슬이 구멍에 들어갈 경우 실패한 방법이기 때문에 더 이상 진행시키지 않고, 오직 빨간색 구슬만 구멍에 들어갔을 때의 횟수를 출력
- bfs 탐색에서 방문 체크는 필수이기 때문에 기존의 boolean 2차원 배열이 아닌 Node 2차원 배열을 이용
- 빨간 구슬, 파란 구슬 각각의 방문 체크가 아닌 해당 순간의 빨간 구슬, 파란 구슬의 위치를 짝지어 방문 체크 해야하기 때문에 빨간 구슬의 좌표를 기준으로 visit에 들어있는 노드의 파란 구슬 좌표가 같다면 이미 탐색 했었던 경우임을 확인하는 방식
- 10번 이하에서 빨간 구슬만 구멍에 통과하면 이동 횟수를 출력하고 아니면 -1

 

⭕️ 2573번 : 빙산 (골드4)

• 문제 유형 : implementation, graph, dfs, bfs
• 시간 복잡도 : O(t*nm)
• 풀이 방식 :

- 2중 for문을 이용하여 빙산 노드를 탐색
- 탐색한 빙산 노드부터 시작하여 bfs 탐색을 시작
- 현재 노드의 주변 노드가 바다면 노드의 값과 전체 총 빙산 값을 -1 하고, 빙산이면 queue에 추가
- 현재 노드로부터 4방향 탐색이 끝났다면 현재 빙산 수치를 탐색한 빙산 총값을 의미하는 변수에 더한다
- bfs 탐색을 총 빙산 수치가 0이 될 때까지 진행하며 만약 queue가 비었을 때 탐색한 빙산 값과 남은 총 빙산 수치가 다르다면 빙산이 두 덩어리 이상 존재하는 것이기 때문에 반복문을 즉시 종료

 

⭕️ 9328번 : 열쇠 (골드1)

• 문제 유형 : implementation, graph, dfs, bfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 빌딩 전체를 돌기만 하면 되기 때문에 dfs, bfs 탐색 모두 가능
- 4방향 탐색을 하는 bfs 탐색
- 가장자리에 입구들이 존재하기 때문에 본 탐색 시작 전에 아래의 규칙과 동일하게 가장자리 노드부터 탐색
- 사전에 가지고 들어간 열쇠를 입력 받고 리스트에 저장되어 있는 문(가장자리에서 우선 탐색 된 문)들을 모두 큐에 넣음
- 탐색 중 열쇠를 만났을 경우 열쇠 배열에서 해당하는 열쇠를 true로 하고 리스트에 저장되어 있는 (열쇠가 없을 때 만나서 임시로 저장해둔 문들) 해당 열쇠로 열 수 있는 문들의 위치를 모두 큐에 넣음
- 탐색 중 문을 만났을 경우 적합한 열쇠를 가지고 있으면 4방향 탐색을 하고, 열쇠가 없을 경우 추후에 적합한 열쇠를 찾을 수 있기 때문에 리스트 해당 자리에 저장해 놓음 (2차원 리스트 이용)

 

⭕️ 15686번 : 치킨 배달 (골드5)

• 문제 유형 : implementation, bruteforce
• 시간 복잡도 : O(xCm*nm)
• 풀이 방식 :

- 전체 치킨 집 개수 x개 중에서 m개의 치킨집을 고르기 위해 벡트레킹 이용
- m개의 치킨 집의 위치를 배열에 저장하고 각 집마다 치킨 집들과의 거리를 모두 구한 후 치킨 거리(가장 작은 값)를 모두 더한 후 모든 집들의 기존에 구했던 치킨 거리 값보다 작으면 저장
- 모든 경우의 치킨집 조합의 치킨 거리를 구했으면 최소 도시의 치킨 거리 출력