BFS

2023년 11월 10일 알고리즘 문제풀이 문제 게임 맵 최단 거리 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import deque def solution(maps): answer = -1 n = len(maps) m = len(maps[0]) da = [1,-1,0,0] db = [0,0,1,-1] maps[0][0] = 0 q = deque() q.append([0,0,0]) while q: a,b,cnt = q.popleft() if a == n-1 and b == m-1: answer = cnt+1 print(a,b) return answer for i in range(4): na = a + da[i] nb = b + db[i] if na < 0 or na >= n or nb < 0 or nb >= m or not maps[na][nb]: continue q.append([na,nb,cnt+1]) maps[na][nb] = 0 return answer BFS를 이용해서 특정 조건(맵 상 벽이라던가, 맵 범위 밖이라던가, 방문한 곳이라던가)을 제외하여 최단 거리를 구하는 문제는 이제 충분히 적응됐다. ...

2023년 9월 2일 알고리즘 문제풀이 문제 1 백준 1948 문제 링크 1차 시도 나의 생각 위상정렬을 이용해 풀고자 하였다. 단 시작지점은 진입차수가 0인 것이 문제의 조건이므로 큐에 시작도시를 넣고 반복하였다. 결국 도착지에 갈때까지 비용을 계속 더해주고, 간선을 이용할 떄마다 카운트 해주었다. 예제를 입력했을 떄 결과값이 실제 정답보다 크게 나오기도 했고, 경로 탐색이 내가 예상한대로 되지 않았다. 아무래도 문제를 제대로 이해하지 못한채 그냥 위상정렬만 적용해서 해결하지 못하고 있는것 같다. 애초에 이 문제를 왜 위상정렬로 풀어야 하는지도 모르겠다.. 공부해봐야겠다. ...

2023년 8월 31일 알고리즘 문제풀이 문제 1 백준 16439 문제 링크 1차 시도 나의 생각 세 종류의 치킨을 고르는 것은 조합(Combination)을 이용했다. 근데 라이브러리를 사용하지 않고 3중 for문으로 구현했다. 라이브러리 쓰는 법도 익혀야지.. 어쩄든 한 사람은 세 종류의 치킨 중 선호도가 가장 높은 것으로 점수를 나타내니 최소힙을 이용하되 음수로 바꾼 후 넣은 후 heappop하여 점수를 구했다. 그리고 각 조합 때마다 현재까지 최고 점수랑 비교하며 업데이트 해주었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import sys from heapq import heappop, heappush n, m = map(int, sys.stdin.readline().split()) graph = [] for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split()))) def cal(): max_val = 0 for i in range(m): for j in range(m): if j == i: continue for k in range(m): ans = 0 if k == i or k == j: continue for person in range(n): arr = [] heappush(arr, -1*graph[person][i]) heappush(arr, -1*graph[person][j]) heappush(arr, -1*graph[person][k]) tmp = heappop(arr) tmp *= -1 ans += tmp max_val = max(max_val, ans) return max_val answer = cal() print(cal()) 문제 2 백준 1939 문제 링크 ...

2023년 8월 25일 알고리즘 문제풀이 문제 1 백준 3055 문제 링크 1차 시도 나의 생각 물을 따로 생각하지 말고 이미 방문해서 방문할 수 없는 곳으로 처리한다면 크게 복잡하지 않을 수도 있겠다는 생각을 했다. 따라서 고슴도치가 이동할 곳을 BFS로 탐색하되, 방문처리를 통해 물이 있는 곳과 바위가 있는 곳을 표시하면 되겠다고 생각했다. 주어진 예시는 답을 출력했는데, 고슴도치가 다음 턴에 물이 찰 곳으로 이동할 수 없는 조건이 적용되지 않았다. 따라서 이동할 수 없는 경우가 누락되어 오답처리되었다. ...

2023년 8월 24일 알고리즘 문제풀이 문제1 백준 1916 문제 링크 1차 시도 나의 생각 이전에 공부한 다익스트라로 풀면 되겠다고 생각했다. 출발지부터 각 도착지까지 비용을 표시하는 배열을 만들고 최소값으로 업데이트하였다. 그런데 이상하게 오답처리가 된다. 이유를 찾아봐야겠다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) graph = [[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(m): s, a, c = map(int, sys.stdin.readline().split()) graph[s][a] = c start, arrive = map(int, sys.stdin.readline().split()) def search(x): cost = [10**9 for _ in range(n+1)] cost[x] = 0 arr = [] heappush(arr,[0, x]) while arr: price, now = heappop(arr) if price > cost[now]: continue for i in range(1, n+1): if not graph[now][i]: continue new_money = price + graph[now][i] if new_money < cost[i]: cost[i] = new_money heappush(arr,[new_money, i]) return cost ans = search(start) print(ans[arrive]) 2차 시도 나의 생각 원인을 찾아냈다. 나는 두 도시간의 비용을 인접행렬로 표현했다. 즉 행렬의 값이 두 도시의 이동 비용이다. 하지만 문제에서 각 도시 간의 노선이 하나라는 보장이 없다.. 그래서 두 도시간의 버스 비용이 중복해서 주어진다면 내 코드는 가장 마지막에 입력된 것만 나타내게 된다. 하지만 먼저 입력된 버스비용이 더 작다면? 내 코드에선 정답을 도출할 수 없었다. ...

2023년 8월 12일 알고리즘 문제풀이 문제 1 백준 18352 문제 링크 1차 시도 나의 생각 도시까지의 최단거리만 생각해야 하므로, bfs를 통해 도착한 도시에 얼마나 걸렸는지를 표시하고, 이를 방문표시로 이용하면 되겠다는 생각을 했다. 출발한 도시 와 도착지가 같을때는 0으로 표시하게 되는데, 이것 때문에 아직 방문처리하지 않은 것으로 취급되어 여러가지로 헷갈렸다. 따라서 제자리 거리를 1로 표시하여 모든 도시의 거리를 구하고 모두 1 만큼 감소시켜주었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import sys from collections import deque n, m, k, x = map(int, sys.stdin.readline().split()) graph = [[]for _ in range(n+1)] for _ in range(m): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) ans = [] visited = [0 for _ in range(n+1)] def bfs(s): visited[s] = 1 arr = deque() arr.append(s) while arr: now = arr.popleft() for next in graph[now]: if not visited[next]: arr.append(next) visited[next] = visited[now]+1 bfs(x) ans = [] if k == 0: print(x) else: for i in range(1, n+1): visited[i] -= 1 if i == x: continue if visited[i] == k: print(i) ans.append(i) if not ans: print(-1) 문제 2 백준 2178 문제 링크 ...

2023년 8월 4일 알고리즘 문제풀이 백준 1260 문제 링크 1차 시도 나의 생각 오랜만에 dfs, bfs라 당황했다. 우선 2차원 배열로 그래프를 그린 후 두 정점 사이의 간선이 있으면 1, 없으면 0으로 표현했다. 그리고 방문한 정점을 표시하기 위한 배열도 만들었다. dfs는 이동할 수 있는 다음 정점으로 재귀를 통해 확인하는 과정을 거쳤다. bfs는 현재 정점에서 이동할 수 있는 정점 모두를 deque에 담은 후 popleft하면서 각각마다 그 다음 목적지를 확인하였다. bfs를 큐로 관리하는 것이 기억해내느라 푸는데 시간이 촉박했다. ...

1.개발 진행 및 완료상황 3주차 python algorithm 그래프 탐색 기본 개념 공부 3주차 python algorithm 그래프 탐색 기본 문제 풀이 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 1991 1991번: 트리 순회 1991번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 트리 순회 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 43388 28410 21707 66.502% 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 … ...