본문 바로가기

👨‍💻📱✍️🎢314

BOJ 7562 - 나이트의 이동 문제 백준 온라인 저지 - 7562번 풀이 과정 나이트가 이동할 수 있는 방향을 통해 목표 지점에 도달하는 최소 이동 횟수를 찾아주는 문제입니다. 이동할 수 있는 방향이 8가지라는 점을 제외하면 일반적인 BFS 탐색 풀이법으로 해결할 수 있습니다. 코드 import sys from collections import deque T = int(input()) test_case = [] for _ in range(T): L = int(input()) cur = list(map(int, sys.stdin.readline().split())) goal = list(map(int, sys.stdin.readline().split())) test_case.append([L, cur, goal]) dx = [-1, -.. 2021. 3. 18.
BOJ 18352 - 특정 거리의 도시 찾기 문제 백준 온라인 저지 - 18352번 풀이 과정 특정 지점에서 목표 지점에 도달하기 위한 최단 거리들 중에서 K 인 정점들을 찾는 문제입니다. 처음에는 단순한 BFS 문제인줄 알고 접근했다가 최단 거리를 구하는 시점 때문에 자꾸 오답이 발생해서 삽질을 하다가 다익스트라 로 다시 접근해서 문제를 해결했습니다. 코드 import sys from collections import deque N, M, K, X = list(map(int, sys.stdin.readline().split())) edges = [list(map(int, sys.stdin.readline().split())) for _ in range(M)] def make_graph(): graph = [[] for _ in range(N + .. 2021. 3. 18.
BOJ 16173 - 점프왕 쩰리(small) 문제 백준 온라인 저지 - 16173번 풀이 과정 시작 지점에서 목표 지점까지의 도달 가능성 유무를 판단하는 문제입니다. BFS 를 이용해서 각 칸의 이동력에 따라 탐색을 수행하면 됩니다. 코드 import sys from collections import deque N = int(input()) board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(sx, sy): q = deque() visit = [[0] * N for _ in range(N)] q.append([sx, sy]) while q: x, y = q.popleft() if board.. 2021. 3. 18.
BOJ 2096 - 내려가기 문제 백준 온라인 저지 - 2096번 풀이 과정 전형적인 DP 문제이지만 메모리 제한이 빡셉니다. 슬라이딩 윈도우 를 활용해서 memo 2차원 배열을 2 * 3 의 크기로 지정해서 값을 구하면 되는데 문제는 처음에 top-down 방식으로 접근했다가 board 배열의 크기를 줄일 방법이 없어서 계속 메모리 초과가 발생했습니다. 대신에 bottom-up 방식으로 변경하고 board 를 미리 입력 받는 것이 아니라 한 줄씩 입력 받아서 사용하는 것으로 변경하여 문제를 해결할 수 있었습니다. 코드 import sys N = int(input()) def solution(): min_memo = [[-1] * 3 for _ in range(2)] max_memo = [[-1] * 3 for _ in range(.. 2021. 3. 18.
BOJ 14716 - 현수막 문제 백준 온라인 저지 - 14716번 풀이 과정 현수막 내부에서 인접한 1 을 탐색해 모든 글자들의 개수를 찾는 BFS 문제입니다. 복잡한 규칙 없이 각 좌표를 탐색하며 아직 방문하지 않은 1 이 발견되면 BFS 를 수행하고 글자 수를 증가시키면 됩니다. 코드 import sys from collections import deque M, N = list(map(int, sys.stdin.readline().split())) board = [list(map(int, sys.stdin.readline().split())) for _ in range(M)] dx = [-1, -1, -1, 0, 1, 1, 1, 0] dy = [-1, 0, 1, 1, 1, 0, -1, -1] def bfs(x, y, visit.. 2021. 3. 18.
BOJ 14923 - 미로 탈출 문제 백준 온라인 저지 - 14923번 풀이 과정 시작 지점에서 목표 지점에 도달하는 최단 경로를 찾는 BFS 문제입니다. 단 벽이 존재할 경우 1회에 한해서 벽을 부수고 이동할 수 있기 때문에 상태 공간을 다음과 같이 정의합니다. visit[x][y][magic] : (x, y) 지점에 남은 마법의 횟수 magic 을 이용하여 도달 한 경우가 있는지 이후 목표 지점에 도달하면 거리 바용을 반환하면 됩니다. 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) Hx, Hy = list(map(int, sys.stdin.readline().split())) Ex, Ey = list(map(.. 2021. 3. 18.

티스토리툴바