[BOJ] 백준 12851 숨바꼭질 2 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다. 가장 빠른 시간으로 찾아가는 방법이 총 몇 가지인지도 구해야 하는 것이 포인트이다. 현재 경로까지의 cnt가 다음 경로에도 합산이 되므로 마치 부분적으로 dp 문제와 같은 느낌이 들었다. 구현 언어: Python from collections import deque def solve(): global n, k, sec, cnt queue = deque() queue.append(n) # 시작점을 먼저 담는다. sec[n] = 0 cnt[n] = 1 while queue: now = queue.popleft() for n..

→2021.01.12

[BOJ] 백준 1697 숨바꼭질 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다. 주의해야할 점이 있었다. 1. (현재 위치, 거기까지 걸린 초) 를 튜플로 큐에 저장해서 사용 각 선택지가 이동하는 방법에 따라 시간이 다르므로, 이동하는 것에 따라 걸린 시간을 같이 보관했다. 2. 방문 체크가 필수이다. 방문했던 지점을 다시 밟는 것은 의미없는 것이다. 실컷 이동하다가 다시 같은 지점을 밟는 것은 결코 최소 거리가 될 수 없다. (+ 시간 초과 100%...) 구현 언어: Python from collections import deque from sys import stdin def solve(): ..

→2021.01.07

[BOJ] 백준 7569 토마토 / BFS

💭 문제 이해 역시 탐색문제로 BFS를 이용하여 풀어야 한다. 여섯 방향으로 동시에 진행하므로 너비 우선 탐색이 맞다고 판단하였다. 다른 문제와 차이점이라면 3차원 리스트를 이용하여야 한다는 점인데, arr[깊이][가로][세로] 인 것을 유의하여야 하는 문제이다. 구현 언어: Python import sys from collections import deque # 3차원 리스트는 arr[깊이][가로][세로]로 구성 # col, rol, height m, n, h = map(int, sys.stdin.readline().rstrip().split()) warehouse = [[list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)] ..

→2021.01.05

[BOJ] 백준 2644 촌수계산 / BFS, DFS

💭 풀이 과정 탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다. 입력으로 주어진 연결 관계를 2차원 리스트로 양 쪽 모두에 저장한다. visited 리스트에는 출발점에서 해당 번호의 노드까지 이동하는 거리(촌수)를 저장한다. visited의 도착점 위치 값이 0이면 가족 관계가 전혀 없다는 뜻이므로 -1을 출력하고, 값이 존재한다면 그 촌 수를 출력한다. 작성언어: Python BFS from sys import stdin from collections import deque n = int(stdin.readline().rstrip()) man1, man2 = map(int, stdin.readline().rstrip().split()) m = int(stdin.readline().rs..

→2021.01.05

[BOJ] 백준 2667 단지번호붙이기 / BFS, DFS

💭 풀이 과정 탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다. N의 크기가 최대 25로 매우 작다. 그러므로 n2의 방법으로 모든 공간을 탐색하며 집이 있는 공간인 1을 발견하면 그 지점에서 탐색을 시작한다. 탐색을 마치고 구해진 크기(단지 크기)를 리스트에 append한다. 모든 연산이 마치면 리스트에는 단지들의 크기가 저장된다. 리스트의 길이가 단지 수가 되고, 리스트를 오름차순 정렬하여 원소들을 출력하는 것으로 마친다. 작성언어: Python BFS from sys import stdin from collections import deque n = int(stdin.readline().rstrip()) square = [list(map(int, list(stdin.readline..

→2021.01.04

[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

💣 문제 이해 문자열 처리를 필요로 하는 문제이다. 주어진 문자열에서 1개 단위, 2개 단위, 3개 단위, 등으로 문자열을 자를 때, 연속된 문자열을 2a2ba3c와 같이 압축한다. 연속된 문자가 1 자리인 경우, 앞에 숫자를 생략하고 문자만 기입한다. 💭 풀이 과정 작성 언어: Python3 def solution(s): answer = 9999 size = len(s) # 한 자리 문자열의 경우 바로 결과 출력 if size == 1: return 1 for i in range(1, size // 2 + 1): temp = s[:i] count = 0 compressed = '' for x in range(0, size, i): if s[x:x + i] == temp: count += 1 else: ..

→2020.09.01

[BOJ] 백준 7576 토마토 / 너비 우선 탐색(BFS)

💣 문제 이해 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성한다. 너비 우선 탐색(BFS) 기법으로 풀이했다. 💭 풀이 과정 작성 언어: Python from collections import deque def bfs(t_m, t_n, t_box): day = -1 mx = [-1, 1, 0, 0] my = [0, 0, -1, 1] while riped_index: # 하루 씩 증가 day += 1 queue_size = len(riped_index) for _ in..

→2020.08.31

[2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임

💣 문제 이해 인형을 집어 올릴 위치에서 0이 아닌 숫자가 나올 때까지 아래 방향으로 탐색한다. 바닥에 도착하기 전에 인형을 발견하면 해당 위치를 0으로 만들고 바구니에 담는다. 만약, 이전에 바구니에 넣은 인형과 같다면, answer를 2 증가하고, 바구니의 그 인형을 제거한다. 💭 풀이 과정 작성 언어: Python3 def solution(board, moves): answer = 0 stack = [] length = len(board[0]) for j in moves: for i in range(length): if board[i][j - 1] != 0: if len(stack) != 0 and stack[-1] == board[i][j - 1]: answer += 2 stack.pop() el..

→2020.05.01