본문 바로가기

코딩테스트 문제풀이/beakjoon64

[백준] 2206 벽 부시고 이동하기 [백준] 2206번 벽 부시고 이동하기 그래프 / 너비우선탐색 [문제] 상하좌우로 이동하는 bfs문제 벽을 부시고 이동할 수 있는 경우가 있다는 것이 핵심이 됨. [과정] 문제를 보면 벽을 나중에 뚫는게 이득일 수 도 있고 아닐수 도 있으므로 해당 부분도 고려해야 함 이 문제는 다른 bfs과는 다르게 벽을 통과했는지 통과하지 못했는지의 상태도 같이 저장함 즉 visited에서 기존의 visited[x][y]가 -> visited[x][y][cnt]와 같은 형식으로 수정해야 하는 것! cnt 부분에는 벽을 통과한 상태인지 아닌지를 판별할 수 있도록 0과1로 정의하는 형식으로 진행함 visited에 [0,0]의 형식으로 벽을 부신 상태의 값과 벽을 부시지 않은 상태의 값을 각기 저장 bfs()수행 최종 거리.. 2022. 7. 14.
[백준] 5427 불 [백준] 5427번 불 그래프 / 너비우선탐색 [문제] 너비우선탐색인 bfs문제 불은 상하좌우로 증식하고 상근이는 상하좌우중 한군데로 이동가능한 것 그리고 하나 짚고 넘어가자면 '상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.'와 '상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.'를 보면 불을 먼저 이동시키고난 후에 상근이를 이동시켜야 함을 알 수 있음! 생각보다 까다로웠다. [과정] 내가 했던 풀이에서는 입력받은 배열(arr)의 외곽에 -1을 둘러서 상근이가 -1위치로 이동하게 되면 정답을 출력하는 형식이었다. 사실 이제와서 생각해보면 어차피 벽으로 둘러쌓여 있으므로 상근이가 배열(arr)의 인덱스를 벗어나면 정답을 출력해도 된다.. 2022. 7. 13.
[백준] 7562 나이트의 이동 백준 7562번 나이트의 이동 그래프 / 너비우선탐색 [문제] bfs를 돌리고 이동할때마다 +1을 해주면 되는 문제 [과정] 핵심이 되는 부분은 나이트가 이동할 수 있는 좌표를 nx,ny로 두는 것 기존은 보통 상하좌우로 이동했었던 부분을 해당 그림의 이동거리에 맞게 좌표를 넣어주고 bfs를 수행하면 됨 입력받는 부분에서 arr배열을 0으로 체스판길이 만큼 초기화 = l or ny >= l: continue if arr[nx][ny] == 0: q.append((nx,ny)) arr[nx][ny] = arr[x][y] + 1 for _ in range(int(input())): l = int(input()) x1, y1 = map(int, input().split()) x2, y2 = map(int, i.. 2022. 7. 11.
[백준] 2887 행성터널 백준 2887번 행성터널 그래프 이론 / 정렬 / 최소 스패닝 트리 [문제] [과정] 기본적인 크루스칼의 2중 반복을 쓰면 메모리에서 초과가 발생 터널로 연결할 때 드는 비용을 보면 x와 y와 z의 거리중에서 짧은 부분을 edges에 넣으면 되므로 각자 만들어서 반복문을 하나로 하여 i번쨰와 i+1번째의 거리를 비교하여 넣으면 됨 기존의 크루스칼을 쓰게되면 간선의 개수는 n(n-1) / 2 임 간선의 개수를 줄여서 x,y,z를 기준으로 정렬 후 반복을 돌리게되면 간선의 개수는 3(n-1)이 됨 x,y,z의 입력값을 별도의 리스트에 저장 x,y,z의 리스트를 정렬 n번의 반복문을 수행하면서 x,y,z에서 i번째와 i+1번째의 거리를 비교하여 비용과 좌표값을 저장 [소스코드] # 행성터널 import sys.. 2022. 7. 10.
[핵심유형] 여행계획 여행계획 그래프 / 서로소 집합 [문제] 간선 정보가 나와있고 집합과의 관계를 파악하기 위하여 서로소 집합 알고리즘을 사용해야 함 [과정] 서로소 집합 수행 i번째 부모와 i+1번째 부모를 순차적으로 돌면서 같은지 확인 [소스코드] # 여행계획 def find_parent(parent, x): if parent[x] != x: return find_parent(parent, parent[x]) return x def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b n,m = map(int, input().split()) paren.. 2022. 7. 9.
[University of Ulm Local Contest] 어두운 길 University of Ulm Local Contest - 어두운 길 그래프 / 최소신장트리 / 크루스칼 [문제] 모든 연결이 필요하고 최대 금액을 출력하는 문제이므로 그래프의 최소신장 트리 - '크루스칼'을 사용하면 됨 출력할 답은 '전체 비용 - 최소비용연결'으로 나타내면 됨 기본적인 크루스칼 문제인듯 [과정] 크루스칼 수행 전체 간선의 비용 - 크루스칼 결과 -> 출력 [소스코드] # 어두운 길 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = f.. 2022. 7. 9.
[CCC] 탑승구 CCC 탑승구 그래프 / 서로소 집합 [문제] [과정] 기본적으로 서로소 집합 문제 비행기 번호에 맞는 탑승구(루트)에 도킹 도킹할 수 없다면 비행기 번호 -1의 탑승구에 도킹 할 수 있는지 확인 탑승구(parent)가 0이 될 때까지 도킹하지 못하면 공항 운행을 중지시키고 도킹한 개수를 출력 [소스코드] # 탑승구 def find_parent(parent, x): if parent[x] != x: return find_parent(parent, parent[x]) return x def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] .. 2022. 7. 8.
[K대회] 정확한 순위 K대회 정확한 순위 플로이드 / 최단거리 [문제] [과정] 자기자신의 간선 비용은 0으로 초기화 간선정보 입력 플로이드 워셜 알고리즘 수행 수행된 결과 출력 -> graph[a][b]와 graph[b][a]가 연결되어있는지 확인 [소스코드] # 정확한 순위 2022-06-29 import sys input = sys.stdin.readline INF = int(1e9) n,m = map(int, input().split()) graph = [[INF] * (n+1) for _ in range(n+1)] # 자기자신 비용 0으로 초기화 for i in range(1, n+1): for j in range(1, n+1): if i == j: graph[i][j] = 0 # 간선정보 입력 for i in ra.. 2022. 6. 30.
반응형

티스토리툴바