⭕️ 16236번 : 아기 상어 (골드3)
- 문제 유형 : graphs, bfs, implementation, simulation
- 시간 복잡도 : O(n^2)
- 풀이 방식 :
- 상어가 먹을 수 있는 물고기들을 선택할 때 가장 가까운 거리에 위치한 물고기 중 선택해야하기 때문에 bfs를 이용
- 거리가 같은 물고기일 경우 가장 왼쪽에 위치한 물고기, 왼쪽 거리도 같다면 가작 위쪽에 위치한 물고기를 선택해야하기 때문에 이에 맞게 우선순위큐의 compare 조건을 지정
- 떨어진 거리가 물고기들만 우선순위 큐에 들어가야하기 때문에 현재 큐의 크기만큼만 빼내어 탐색
- 거리 1당 시간이 1씩 걸리기 때문에 선택한 물고기로 이동할 때마다 떨어진 거리(물고기까지의 bfs시행 횟수)만큼 더하여 총 이동 시간을 구한다
❌ 2206번 : 벽 부수고 이동하기 (골드3)
- 문제 유형 : graph, bfs
- 시간 복잡도 : O(nm*2)
- 풀이 방식 :
- 시작 지점으로부터 목표 지점까지의 최소 거리를 구하는 문제이기 때문에 기존의 bfs 풀이방식을 이용
- 벽을 1개를 부숴 길을 만들 수 있기 때문에 벽을 부수고 이동했을 때 보다 벽을 부수지 않고 이동했을 때가 더 최소값인 경우 기존의 visit배열을 사용했을 경우 탐색 불가
- 기존의 visit 배열과는 다르게 벽을 부수지 않고 이동했을 때, 벽을 1개 부수고 이동했을 때의 visit배열을 따로 관리하기 위해 3차원 배열을 이용(visit[n][m][2])
⭕️ 14442번 : 벽 부수고 이동하기2 (골드2)
- 문제 유형 : graph, bfs
- 시간 복잡도 : O(nmk)
- 풀이 방식 :
- 2206번과 동일한 방법으로 visit 배열을 벽의 제한 갯수의 크기로 만들어 주고, 각 정점 방문시 따지는 조건 또한 갯수 제한에 따라 바꿔줌(visit[n][m][k])
⭕️ 16933번 : 벽 부수고 이동하기3 (골드1)
- 문제 유형 : graph, bfs
- 시간 복잡도 : O(nmk)
- 풀이 방식 :
- 14442번 벽 부수고 이동하기2의 풀이 방법 이용
- 기존에 벽을 만나면 제한 횟수 내에서 무조건 부실 수 있었지만 아침에만 벽을 부술 수 있기 때문에 큐에 넣는 노드 클래스에 아침인지 밤인지 체크하는 boolean 타입의 변수를 추가
- 벽을 만났을 때 아침이면 기존과 똑같이 벽을 부수고 이동하고, 밤이면 제자리에서 아침까지 한 번 멈췄다 가야하기 때문에 현재 위치에서 이동거리를 1번 늘리고 아침 상태로 바꾸어 큐에 다시 집어 넣음
- 두 번째로 생각해낸 벽을 만났을 때 밤이면 바로 부숴 이동하는 대신 아침까지 기다렸다는 의미로 거리를 2번 늘려 큐에 집어넣는 방법은 실패 -> 아침까지 기다렸다가 벽을 부숴 이동하는 경로 대신 다른 경로가 최소 거리일 수 있는데, 벽을 만나는 즉시 이동거리를 2번 늘려 큐에 넣을 경우 최소 경로보다 앞서 들어갈 수 있어 결과가 최소 거리가 아닐 수 있기 때문
- 최소거리를 구할 때 큐를 이용한 bfs 탐색을 하는 이유는 같은 거리만큼 떨어진 노드들이 같은 사이클에 큐에 들어가서 거리 기준 오름차순으로 큐에 쌓이게 되어 목적지와 동일한 좌표를 가진 첫 번째 순간을 최소 라 확신할 수 있기 때문인데 두 번째 방법에 경우 이 원리를 해침 (두 번째 방법을 사용하기 위해선 노드에 저장되어 있는 이동 거리를 기준으로 오름차순 정렬하는 우선순위 큐를 사용하는 bfs탐색 이용)
⭕️ 9328번 : 벽 부수고 이동하기 4 (골드2)
- 문제 유형 : implementation, graph, dfs, bfs
- 시간 복잡도 : O(nmk)
- 풀이 방식 :
- 벽을 하나 지우고 이동 할 수 있는 칸 수를 각 벽마다 구해야하기 때문에 dfs, bfs 탐색 둘 다 가능
- 모든 벽마다 bfs 탐색을 하면 O((nm)^2)이 되기 때문에 상당한 시간이 걸림
- 시간을 줄이기위해 벽으로 막히지 않고 연결된 길들의 개수를 세서 하나의 그룹으로 모두 묶음 (Node 2차원 배열을 만든 뒤 탐색을 시작한 노드를 기준으로 연결된 모든 노드에 시작 노드를 저장하고 시작 노드의 이동 가능 칸수를 늘림 -> 그룹화)
-벽을 지우고 4방향으로 벽이 아닌 길이 존재한다면 미리 구해둔 그룹의 개수를 바로 더함 (방문한 길의 Node 2차원 배열에 들어있는 노드을 확인해 이동 가능 칸 수를 바로 구함)
- 단순하게 4방향에서 더하면 그룹이 중복 되어 세질 수 있기 때문에 리스트에 방문한 그룹을 저장해두고 만약 인접한 그룹이 리스트 안에 있는 그룹(이미 방문한 그룹)일 경우 더하지 않고 넘어감
- 벽을 지우고 이동 할 수 있는 칸 수를 따로 2차원 배열(그래프)에 저장하고 출력
❌ 1726번 : 로봇 (골드3)
- 문제 유형 : graph, bfs
- 시간 복잡도 : O(nm*4)
- 풀이 방식 :
- 제자리에서 오른쪽 또는 왼쪽으로 방향을 바꿀 때 이미 탐색한 경우임을 체크하기 위해 방문 체크용 visit배열을 동, 서, 남, 북 4가지 경우를 각각 고려할 수 있도록 3차원으로 이용
- 직선 방향으로 1~3칸 이동할 수 있는데 만약 앞에 벽이 존재하면 이후로 이동할 수 없기 때문에 break, 이미 방문한 칸이면 continue하여 모든 경로를 탐색
- 메모리 초과 이유 : visit배열을 2차원 배열로 사용하더라도 최소 동작 횟수는 구할 수 있지만 제자리에서 빙빙 도는 경우의 노드들이 계속해서 큐에 들어가 메모리 초과가 일어남
- *틀린 이유 : 만약 한 칸 앞이 이미 방문한 노드일지라도 두 칸, 세 칸 앞의 노드는 방문하지 않은 노드일 때 최소 경로가 될 수 있기 break이 아닌 continue를 해야하지만 아무 생각 없이 벽이 있을 때와 똑같이 break을 해버림
- 큐에서 빼낸 노드의 좌표와 방향이 같을 때의 동작 횟수를 출력
⭕️ 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
⭕️ 2638번 : 치즈 (골드3)
- 문제 유형 : graph, bfs, dfs
- 시간 복잡도 : O(t*nm)
- 풀이 방식 :
- 가장자리는 항상 치즈(1)이 없기 때문에 가장자리부터 연속적으로 이어지는 치즈가 아닌 빈 블록을 활용하는 방법을 사용하기 때문에 bfs와 dfs 모두 가능
- visit 배열뿐만이 아니라 치즈의 공기 노출면의 개수를 체크하는 check 배열을 사용
- (0, 0)부터 bfs 탐색을 시작하여 (i, j)가 공기(0)일 경우 queue에 집어 넣고, 치즈(1)일 경우 check[i][j]가 이미 true일 때는 해당 치즈를 없애고, false일 때는 공기 노출면이 적어도 하나 존재함을 나타내기 위해 check[i][j]를 true로 바꿔준다
- 과정 반복 중 queue가 비었을 경우 1시간이 지나 공기 접촉면이 2개 이상인 테두리 치즈들이 녹은 것을 뜻하기 때문에 while문을 하나 더 이용하여 삭제 된 치즈의 개수가 처음 입력 받은 치즈의 총 개수와 같아질 때, 즉 모든 치즈가 삭제될 때까지 반복하여 총 시간을 구한다
⭕️ 9328번 : 열쇠 (골드1)
- 문제 유형 : implementation, graph, dfs, bfs
- 시간 복잡도 : O(nm)
- 풀이 방식 :
- 빌딩 전체를 돌기만 하면 되기 때문에 dfs, bfs 탐색 모두 가능
- 4방향 탐색을 하는 bfs 탐색
- 가장자리에 입구들이 존재하기 때문에 본 탐색 시작 전에 아래의 규칙과 동일하게 가장자리 노드부터 탐색
- 사전에 가지고 들어간 열쇠를 입력 받고 리스트에 저장되어 있는 문(가장자리에서 우선 탐색 된 문)들을 모두 큐에 넣음
- 탐색 중 열쇠를 만났을 경우 열쇠 배열에서 해당하는 열쇠를 true로 하고 리스트에 저장되어 있는 (열쇠가 없을 때 만나서 임시로 저장해둔 문들) 해당 열쇠로 열 수 있는 문들의 위치를 모두 큐에 넣음
- 탐색 중 문을 만났을 경우 적합한 열쇠를 가지고 있으면 4방향 탐색을 하고, 열쇠가 없을 경우 추후에 적합한 열쇠를 찾을 수 있기 때문에 리스트 해당 자리에 저장해 놓음 (2차원 리스트 이용)
❌ 16947번 : 서울 지하철 2호선 (골드3)
- 문제 유형 : graph, dfs, bfs
- 시간 복잡도 : O(n)
- 풀이 방식 :
- 1번째 노드부터 재귀함수를 이용한 dfs 탐색을 시작
- (인접 리스트 이용)현재 노드와 연결된 노드가 이미 방문 했었고 이전 노드와 같지 않을 때(탐색 중 재방문을 거르기 위함) 사이클이 존재
- 최초로 사이클이 발견 됐을 때의 노드가 사이클이 시작되는 노드이기 때문에 따로 저장
- 재귀된 함수들을 역으로 올라가면서 현재 노드가 시작노드와 다를 경우 시작과 끝 사이에 있는 노드이기 때문에 사이클 요소 임을 체크하고 true 리턴하고, 시작 노드와 같을 경우 현재 노드와 연결된 이외의 노드들은 사이클에 포함되선 안되기 때문에 false 리턴
- 큐에 사이클 내 노드들을 모두 집어 넣고, bfs 탐색을 하며 방문하지 않은 노드 즉, 사이클 내의 요소가 아닌 노드일 때 사이클과 떨어진 거리를 저장 -> 사이클로부터 가장 멀리 떨어진 노드 방향으로 떨어진 거리를 체크할 생각을 하지 못함
- 노드의 개수와 간선의 개수가 같고 모든 노드가 연결 되어 있을 때 무조건 단 하나의 사이클이 존재