🗂️ 문제링크: https://www.acmicpc.net/problem/2468 💡 접근법BFS 알고리즘을 통해 기준 높이보다 지역의 높이가 높아 물에 잠기지 않는 영역의 개수를 구한다. 이를 구하기 위해선 BFS 알고리즘을 통해 인접한 지역(상하좌우)을 탐색할 때 방문하지 않았던 위치(not visited[nx][ny])이면서 기준 높이보다 해당 지역의 높이가 높아야 한다(maps[nx][ny] > h). 지도에서 최대 지역의 높이를 찾아 최대 높이만큼 반복하여 안전한 영역의 최대 개수를 구한다. 😎 내 코드import sysfrom collections import dequeN = int(sys.stdin.readline())maps = []max_height = 0for _ in range(..
🗂️ 문제링크: https://www.acmicpc.net/problem/7562 💡 접근법나이트가 이동할 수 있는 범위를 dx와 dy로 생성한다.이후 맵의 크기에 맞게 False로 maps를 초기화하고, deque를 통해 큐를 생성한다. 초기 시작 위치값인 a와 b를 입력받고, maps[a][b]=0으로 초기화한다.while()문을 통해 큐의 맨 왼쪽 값을 pop하면서 나이트가 이동할 수 있는 범위를 모두 탐색한다. 이때 맵을 벗어나지 않으면서 방문한 적 없는 위치일 경우 큐에 현재 위치를 추가하고 maps에 현재 값을 업데이트한다. 이때 업데이트되는 값은 처음부터 지금까지 이동한 횟수를 나타낸다. 만약 종료 위치에 도달했을 경우 큐를 비워 while문을 빠져나온다.최종적으로 이동하려는 위치에 해당..
🗂️ 문제링크: https://www.acmicpc.net/problem/1966 💡 접근법제일 왼쪽의 값을 쉽게 꺼내기 위해 deque를 사용한다. 문서가 몇 번째로 인쇄되는지 횟수를 세기 위해 인덱스를 저장해야 한다. 이를 위해 queue에 튜플 형식으로 (인덱스, 중요도)를 저장한다.while()문을 통해 큐에서 왼쪽에 위치한 값을 하나씩 꺼내고, 만약 그 다음 값들 중 현재 값보다 중요도가 높은 문서가 있다면 다시 큐에 현재 값을 삽입한다. 이때 인쇄가 될 경우 카운트 횟수를 증가시켜야 한다. 따라서 큐에서 현재 값을 꺼낼 때 카운트를 1 증가시키고, 만약 현재 값보다 중요도가 큰 문서를 발견하여 현재 값을 다시 큐에 삽입하게 되면 카운트를 1 감소시킨다. target에 궁금한 문서를 저장해 ..
🗂️ 문제링크: https://www.acmicpc.net/problem/2667 💡 접근법DFS를 사용하여 연결된 집의 개수를 구한다. 이때 dx와 dy 리스트를 통해 현재 위치에서 상하좌우로 이동할 수 있게 하고, 이동한 좌표가 1) 지도 밖을 벗어나지 않는지, 2) 집이 존재하는지, 3) 방문한 적이 없는지를 확인한다. 모든 조건을 만족할 경우 재귀로 DFS를 수행하고, 수행한 횟수를 cnt로 계산한다.해당 값이 단지에 속하는 집의 개수가 된다. 😎 내 코드import sysN = int(sys.stdin.readline())house_num = []visited = [[False] * N for _ in range(N)]maps = []for _ in range(N): maps.appe..
🗂️ 문제링크: https://www.acmicpc.net/problem/1325 💡 접근법BFS/DFS를 사용하여 각 정점에서 이동할 수 있는 정점들의 최대 개수를 구하는 문제이다."A가 B를 신뢰하는 경우 B를 해킹하면, A도 해킹할 수 있다." 즉, 방향이 있는 그래프를 만들어 B → A 단방향 그래프를 정의해야 한다. 또한 시간복잡도 제한때문에 Python3가 아닌 PyPy3로 제출해야 성공할 수 있다. 😎 내 코드import sysfrom collections import dequeN, M = map(int, sys.stdin.readline().split())graph = [[] for _ in range(N+1)]for _ in range(M): a, b = map(int, sys..
🗂️ 문제링크: https://www.acmicpc.net/problem/1753 💡 접근법가중치가 자연수인 방향 그래프이므로 최단 경로를 구하기 위해 다익스트라를 사용해야 한다. 또한 거리가 가장 작은 노드를 자동으로 선택하기 위해 우선순위 큐(heapq)를 사용한다. distance의 요소는 모두 INF로 초기화되어 있다. 만약 if distance[now_node] 조건을 만족할 경우 now_node는 이미 방문된 노드이므로 방문 처리를 위한 visited 리스트가 따로 필요하지 않다.또한 해당 조건을 만족할 경우 이미 dist는 distance[now_node]보다 큰 값이기 때문에 dist 값으로는 now_node와 연결된 다른 노드의 최단 거리를 구할 수 없다. 따라서 continue를 ..
🗂️ 문제링크: https://www.acmicpc.net/problem/18352 💡 접근법인접 리스트를 통해 그래프를 구현하고, BFS를 사용하여 각각의 도시까지의 최단 거리를 distance 리스트에 저장한다. 현재 노드의 거리 값은 이전 노드의 거리 값 + 1이다.이후 K와 거리가 같은 도시를 출력하면 된다. 😎 내 코드import sysfrom collections import dequedef BFS(v): queue = deque() queue.append(v) visited[v] = True while queue: now_node = queue.popleft() for i in graph[now_node]: if not ..
🗂️ 문제링크: https://www.acmicpc.net/problem/10815 💡 접근법이분탐색 시 탐색 범위를 설정해야 한다. 해당 문제에서는 카드 리스트를 정렬하고, 카드 리스트 인덱스의 최솟값(0)과 최댓값(len(card_list)-1)을 low와 high로 각각 지정한다. mid의 값을 변경하며 탐색한다. 이때 카드 리스트에서 mid 인덱스에 해당하는 값보다 상근이가 가지고 있는 숫자가 작으면 mid 값을 줄여야하므로 high = mid - 1로 설정한다. 반대의 경우엔 mid 값을 키워야하므로 low = mid + 1로 설정한다. 만약 카드 리스트에서 mid 인덱스에 해당하는 값이 상근이가 가지고 있는 숫자와 같다면 1을 저장한다. 😎 내 코드import sysN = int(sys...
