기록

문제 보기 이 문제는 BFS 문제이다. (+ 시간 초과) 백준 문제를 풀면서 시간제한이 6초인 문제는 처음 봤다. 하지만 6초라는 시간도 짧았다. 이 문제는 BFS를 구현하는 것보다 시간을 단축시키는 아이디어가 더 중요하였다. 문제 접근 입력받는 A 값을 큐에 삽입한다. A를 이용해서 D, S, L, R 과정을 수행해보고 가능한 경우는 결괏값을 큐에 삽입한다. 목푯값을 만날 때까지 위 과정을 진행한다. D와 S과정은 시간 초과와 별 상관없어 보였지만 L, R은 어떻게 수행하냐에 따라서 시간과 밀접한 연관이 있을 것이라고 생각했다. 제일 먼저 문자열 연산으로 접근하였지만 시간 초과가 발생하였다. 결국 수식을 활용해서 구하는 해답을 찾아내었으며 통과하였다. 알고리즘 입력받은 A 값을 큐에 삽입한다. 큐의 제..

문제 보기 이 문제는 BFS 문제이다. 문제 접근 현재 층을 큐에 삽입한 후 상, 하로 움직이면서 목표층에 도달할 수 있는지 파악한다. 도달하는 경우 움직인 최솟값을 출력한다. 도달하지 못하는 경우 use the stairs를 출력한다. 알고리즘 현재 층을 큐에 삽입한다. 큐의 제일 앞부분을 pop 한 후 상, 하로 움직일 수 있는지 파악한다. 위의 과정을 목표층을 찾거나, 큐가 빌 때까지 진행한다. 코드 from collections import deque def bfs(F, S, G, U, D): q = deque([[S, 0]]) visited = {S} while q: floor, cnt = q.popleft() if floor == G: # 목표 층에 도착 return cnt if floor +..

문제 보기 이 문제는 bfs 문제이다. (+시간 초과 해결) 문제 접근 인구 차이를 통해서 국경선을 열고 닫으며, 몇 번의 인구 변화가 일어나는지 파악하는 문제이다. 국경선을 열 때마다 인구 변화를 일으키는 것이 아니라 전체 국경선 형태를 파악한 후 한 번에 값을 업데이트한다. (시간 초과 관련) 국경선을 열 수 없을 때까지 진행한다. 알고리즘 현재 위치에서 지나갈 수 있는 집합을 파악한다. (원소 위치, 원소 개수, 원소 합) - bfs 1번의 과정을 전 구간에 실시한다. 값을 업데이트하고 다시 1번으로 돌아간다. 만약 업데이트할 값이 없다면 종료한다. 코드 import sys from _collections import deque # 상, 하, 좌, 우 dy = [-1, 1, 0, 0] dx = [0..

문제 보기 로봇 청소기문제는 시뮬레이션 문제이다. 기존의 bfs 구현에서 아래 2가지를 추가해주면 된다. 1. 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행하기 때문에 현재 방향을 왼쪽방향으로 바꿔주는 함수 2. 현재 방향을 기준으로 후진을 하기 위해서 역방향으로 바꿔주는 함수 위 2가지를 추가해주고 기존의 bfs와 유사하게 코드를 구현하니 통과하였다. 코드 # boj 14503 # blog : jjangsungwon.tistory.com import sys from collections import deque # 북 동 남 서 dy = [-1, 0, 1, 0] dx = [0, 1, 0, -1] # 방향 전환 def change(d): if d == 0: # 북 -> 서 return 3 elif..

문제 보기 bfs와 조합을 응용하여 구현하였다. 지도에서 3개의 벽을 세웠을 때 안전 영역의 최대 크기를 출력하는 문제이다. 조합을 통해서 벽을 세울 위치를 구하였으며, 벽을 세운 후 bfs를 통해서 바이러스를 퍼트렸다. 알고리즘 순서는 다음과 같다. 1. 벽을 세울 수 있는 후보를 찾는다. (배열에서 0 값을 찾는다) 2. 후보 중에서 3개를 고른다. (combinations 내장 함수 이용) 3. bfs 4. 안전 영역의 최대 크기를 업데이트하고 2번으로 돌아간다. (후보 중에서 3개를 고르는 모든 경우를 수행하고 알고리즘은 종료된다) 코드 # boj 14502 # blog : jjangsungwon.tistory.com import sys, copy import itertools from colle..

문제 보기 이 문제는 bfs 문제이다. 수빈이가 3가지 연산을 통해서 동생에게 최대한 빠르게 갈 수 있는 시간을 출력하는 문제이다. 최단 시간과 관련된 문제는 대부분 bfs와 관련이 있는 것 같다. 알고리즘 순서는 다음과 같다. 1. 수빈이의 현재 위치를 큐에 담는다. 2. 현재 위치에서 갈 수 있는 위치를 큐에 담는다(현재 위치 + 1, -1, * 2) 3. 2번 과정을 동생의 위치가 나올 때까지 반복적으로 한다. 위 알고리즘으로 구현을 하여도 시간 초과 혹은 메모리 초과가 발생할 수도 있다. 방문 여부를 확인하는 visited를 list형으로 했을 때 시간 초과가 발생했으며, 큐에 담는 위치를 제한하지 않으면 메모리 초과가 발생하였다. 따라서 방문 여부는 set으로, 큐에 담는 위치는 0 이상 10만..