🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법모든 노드의 가중치가 동일했기 때문에 BFS를 사용하여 최단 거리를 구했다.1번 노드에서 모든 노드까지의 최단 거리를 구하고, 그 중 가장 긴 거리를 구한 뒤, 거리 배열에서 가징 긴 거리의 개수를 구했다. 😎 내 코드from collections import dequedef BFS(v, graph, visited): distances = [0 for _ in range(len(visited))] ..
BFS
🗂️ 문제링크: https://www.acmicpc.net/problem/10026 💡 접근법적록색약인 경우 R과 G를 같은 색으로 취급한다.따라서 BFS를 일반 BFS와 적록색약을 처리하는 BFS 두 함수를 정의하고, 적록색약을 처리하는 BFS 함수에서(color == "R" or color == "G") and (maps[nx][ny] == "R" or maps[nx][ny] == "G") 조건을 통해 R과 G를 같은 색으로 처리한다. 아니면, 적록색약용 맵(R을 모두 G로 변경)을 따로 생성하여 정상인을 처리할 때와 동일한 BFS를 사용할 수도 있다. 😎 내 코드(1) 적록색약 유무에 따른 BFS 함수 분리import sysfrom collections import dequeN = int(sy..
🗂️ 문제https://www.acmicpc.net/problem/2468 💡 접근법영역의 최대 높이를 구한 뒤 0부터 최대높이까지 모든 경우에 대해 안전한 영역의 수를 센다. 이때 안전한 영역의 수를 세기 위해 DFS나 BFS를 통해 지도를 탐색하여 특정 높이보다 해당 영역의 높이가 높다면(maps[nx][ny] > m) 탐색을 계속한다. 그리고 최종적으로 영역의 개수의 최댓값을 출력한다. 또한, 상하좌우로 이어진 것을 하나의 영역으로 보기 때문에 BFS를 썼을 경우에 성능을 더 최적화할 수 있다. 😎 내 코드import syssys.setrecursionlimit(10**6)N = int(sys.stdin.readline())maps = []max_value = 0for _ in range(N)..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🚀 시행착오def solution(m, n, puddles): # m: 열, n: 행 answer = 0 dict = {} # key: 경로, value: 경로 개수 visited = [[False] * (m+1) for _ in range(n+1)] dx = [0, 1] # 아래쪽, 오른쪽 dy = [1, 0] def DFS(y, x, cnt): visi..
🗂️ 문제링크: https://www.acmicpc.net/problem/1697 💡 접근법maps라는 1차원 리스트를 선언하고, BFS를 통해 현재 위치에서 +1, -1, *2칸을 더한 위치를 탐색한다. 이때 방문 처리를 위한 visited라는 리스트는 따로 생성하지 않고, maps가 0인 경우 방문하지 않은 것으로 간주하여 처리한다. 또한, 위치의 범위(0 ≤ N ≤ 100,000)가 정해졌으므로, 이를 기준으로 리스트의 길이와 위치 범위를 벗어났을 때의 처리 조건을 미리 선언해 둔다. 만약 현재 위치가 수빈이의 위치(K)일 경우 조건문을 통해 탈출하고, 현재 위치의 값을 반환한다. 😎 (틀린) 내 코드import sysfrom collections import dequeN, K = map(i..
🗂️ 문제링크: 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://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법최단거리를 구하기 위해 BFS를 사용한다.이때 상하좌우로 이동하면서 맵을 탐색해야 한다. 따라서 변화량을 나타내는 dx와 dy 리스트를 생성한다. 초기 시작 위치를 (0, 0)으로 지정하고, 시작 위치에서부터 상하좌우로 탐색한다. 탐색하면서 조건문을 통해 맵을 벗어나지 않는지, 벽이 아닌지, 방문한 적이 없는지 확인한다.위 조건을 모두 만족할 경우 방문 처리를 수행하고, 맵..
