본문 바로가기

Algorithm202

BOJ 5980 - Corn Maze 문제 백준 온라인 저지 - 5980번 풀이 과정 시작지점에서 목표지점에 도달하기 위한 최소 이동 횟수를 구하는 BFS 문제입니다. 여기서 주의할 점은 특정 지점간의 양방향 포탈이 존재한다는 것입니다. 각각의 포탈은 대문자 알파벳으로 제공되기 때문에 해시 테이블 을 이용해서 각 포탈의 정보를 관리합니다. 또한 중복 방문을 방지하기 위해서 visit 을 체크할 때 포탈의 위치는 중복 방문을 허용해야 한다는 점에 주의합니다. 이렇게 하지 않으면 포탈을 한번밖에 사용하지 못하는 상황이 발생하여 필요할 때 사용할 수 없기 때문입니다. 이로인해 다음과 같은 예시에서 문제가 발생할 수 있습니다. ###### #.WB## #.#### =B@W## ######코드 import sys from collections imp.. 2021. 6. 7.
BOJ 1240 - 노드사이의 거리 문제 백준 온라인 저지 - 1240번 풀이 과정 트리 는 특정 정점에서 다른 정점까지 단 하나의 경로가 존재합니다. 따라서 BFS 를 이용해 각 정점까지의 거리를 구할 수 있습니다. 이때 인접 리스트를 이용해서 그래프를 구현한다면 O(V+E) 의 시간 복잡도로 문제를 해결할 수 있습니다. 코드 import sys from collections import deque def make_graph(edges): graph = {n + 1: [] for n in range(N)} for frm, to, cost in edges: graph[frm].append([to, cost]) graph[to].append([frm, cost]) return graph def bfs(start, goal): q = dequ.. 2021. 6. 7.
BOJ 11265 - 끝나지 않는 파티 문제 백준 온라인 저지 - 11265번 풀이 과정 그래프가 주어졌을 때, 최소 시간으로 각 지점간의 이동 비용을 구한 뒤 제한 시간내에 도달 가능성을 판단하는 문제입니다. 플로이드 와샬 알고리즘 을 사용해서 모든 정점간의 최소 비용을 구한 뒤 시작 지점과 도착 지점을 활용해서 답을 구할 수 있습니다. 코드 import sys def floyd(graph): for k in range(N): for i in range(N): for j in range(N): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) def solution(current_party, next_party, remaining_time): is_possible = graph[curre.. 2021. 6. 4.
BOJ 10472 - 십자뒤집기 문제 백준 온라인 저지 - 10472번 풀이 과정 보드의 최종 상태가 주어질 때, 초기 상태에서 해당 목표 상태에 도달하기 위한 최소 조작 횟수를 구하는 문제입니다. 이를 위해서 BFS 를 이용해 보드의 모든 가능한 상태를 순회해줍니다. 다만 중복된 상태 순회를 피하기 위해서 보드가 검은색으로 칠해져 있을 경우 1 로, 그렇지 않을 경우 0 으로 변환하여 이진수를 생성한 다음, 중복된 상태를 검증합니다. 코드 import sys import copy from collections import deque dx = [0, 1, -1, 0, 0] dy = [0, 0, 0, 1, -1] def convert_board(board, x, y): ret = copy.deepcopy(board) for i in ra.. 2021. 4. 18.
BOJ 13908 - 비밀번호 문제 백준 온라인 저지 - 13908번 풀이 과정 비밀번호에 포함된 숫자들을 알고 있을 때 가능한 모든 경우의 수를 찾는 문제입니다. 백트래킹 을 이용해서 모든 경우의 수를 따져본 다음, 생성된 비밀번호가 조건에 부합하는지 판단하면 됩니다. 코드 import sys def is_valid(password): return all(map(lambda num: num in password, nums)) def dfs(password): if len(password) == n: return 1 if is_valid(password) else 0 ret = 0 for i in range(10): password.append(i) ret += dfs(password) password.pop() return ret .. 2021. 4. 13.
BOJ 14940 - 쉬운 최단거리 문제 백준 온라인 저지 - 14940번 풀이 과정 목표지점에 도달하기 위한 최단거리를 구하는 문제입니다. 2차원 배열의 각 칸을 정점이라고 생각할 경우 모든 인접한 정점까지의 거리 값은 같기 때문에 BFS 를 이용해서 목표지점까지의 최단 거리를 구할 수 있습니다. 코드 import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def find_start(): for x in range(N): for y in range(M): if board[x][y] == 2: return [x, y] def in_range(x, y): return 0 2021. 4. 13.

티스토리툴바