[백준] 16953번 - A → B 풀이 시간: 40분이내 1) 문제 해결 아이디어 리플릿에서 코드를 짜고 실행을 했을 때는 graph크기를 (10**9 _+ 1) 로 생성하니 그냥 종료 되었다. 크기를 수정하니 전혀 문제가 없었으나 제출할 때 메모리 초과 오류가 생겼다. 코드를 짜는 것은 쉬웠는데 오류를 고치는데 시간이 많이 걸렸다. 모든 BFS 문제는 graph를 만들어서 문제를 푼다는 고정관념때문에 틀린 문제였다. 항상 graph를 만들어 문제를 풀다보니 자연스레 또 그래프를 만들 생각만 했던 것 같다. BFS를 풀기 위해서는 큐만 있으면 된다!! 1. 큐 생성 및 (시작값, 누적 연산횟수) 형태로 삽입 2. 2가지 연산 수행 2-1. 큐에서 하나 꺼내기 2-2. 2가지 연산한 결과값(nx)이 1보..
[백준] 2206번 - 벽 부수고 이동하기 풀이 시간: 1) 문제 해결 아이디어 언제 벽을 부숴야 할지 조건을 떠올리는게 쉽지 않았다. 최근에 푼 BFS 문제 중에는 난이도가 가장 높은 문제인 것 같다. 여러가지 아이디어를 떠올려보고 시도해봤으나 잘 되지 않고 시간이 너무 지체되서 풀이를 봤는데도 한 번에 이해가가지 않아 복습이 필요한 문제다. Q. visited 3차원 배열 생성 시 초기화하는 이유는? visited를 생성하는 부분에서 시작 좌표(0, 0)에 해당하는 부분을 1로 초기화해야한다. 그렇지 않으면 (0,1)이나 (1,0)의 인접좌표를 검사할 때 (0, 0)의 graph값이 0이므로 검사를 진행하게 되는 문제가 발생한다. 사실상 정답에 영향을 미치지는 않지만 헷갈리니 그냥 다 초기화하는 걸로..
[백준] 1697번 - 숨바꼭질 풀이 시간: 40분 이내 1) 문제 해결 아이디어 코드를 짜는데는 10분 정도 걸렸는데 오류를 고치는데 시간을 허비했다. 이 문제 같은 경우는 수빈이와 동생의 위치가 N, K로 주어졌을 때 수빈이가 동생을 찾을 수 있는 최소 시간을 구하는 문제로 BFS로 풀 수 있는 문제였다. 이 문제에서는 N, K 값이 해당 범위 내에서 어떤 값이 들어올지 모르기 때문에 입력되는 N, K의 범위를 잘 확인한 후 리스트를 생성해야한다. N, K가 각각 0 이상 100,000 이하로 범위가 주어졌기 때문에 크기가 100,001인 리스트(graph)를 생성했다. 평소에는 범위를 잘 확인하지 않아도 문제를 푸는데 지장이 없는 경우도 많았지만 이 문제의 경우는 주어진 범위를 보고 리스트 크기를 ..
[백준] 7562번 - 나이트의 이동 풀이 시간: 15분 이내 1) 문제 해결 아이디어 시작 위치에서 목표 위치까지 최소 이동 횟수를 구하는 문제로 BFS로 풀 수 있는 대표적인 문제이다. 목표 지점에 도달하면 종료하는 코드는 사실상 없어도 정답이 되지만 있는 게 더 효율적이다. 해당 코드가 없으면 목표 위치에 도달하더라도 방문할 수 있는 좌표가 남아있다면 계속 탐색을 수행하기 때문이다. 1. 시작 지점 삽입, 방문 처리 2. 큐에서 좌표 하나 꺼내기 3. 2번에서 꺼낸 좌표 기준으로 8가지 방향 탐색 2-1. 범위 내이고 방문하지 않은 곳이면 삽입, 방문 처리 4. 목표 좌표가 될 때까지 2~3번 계속 반복 2) 소스코드 import sys from collections import deque # BF..
[백준] 6603번 - 로또 풀이 시간: 10분 이내 (풀이1) combinations 라이브러리 사용 1) 문제 해결 아이디어 집합의 원소 k개 중에서 6개를 뽑는 경우의 수를 모두 출력하는 완전 탐색 문제이다. 전형적인 조합을 구하는 문제로 파이썬의 경우 combinations 라이브러리를 통해 쉽게 구현할 수 있다. 2) 소스코드 from itertools import combinations while True: t = list(map(int, input().split())) k = t[0] # 집합 원소 수 # 종료 조건 if(k == 0): break s = t[1 : len(t)] # 집합 for i in list(combinations(s, 6)): print(" ".join(map(str,..
[백준] 11724번 - 연결 요소의 개수 풀이 시간: 10분 이내 연결 요소의 의미를 몰라서 문제 해결을 할 수가 없어 먼저 연결 요소에 대해 학습하였다. 연결 요소 문제는DFS, BFS로 모두 풀 수 있다. 하지만 직접 코드를 짜본 결과 메모리, 시간 측면에서 둘다 비슷비슷하기 때문에 오류를 고칠 필요가 없는 BFS로 풀기를 추천한다. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다. 연결 요소 개수를 구하는 것은 인접한 정접으로 이루어진 그래프 개수를 세는 것과 같다. [참고] https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Compon..
[백준] 7569번 - 토마토 풀이 시간: 1시간 이내 1) 문제 해결 아이디어 이전 문제(7576번)과 거의 동일한 문제로 이 문제도 BFS를 이용하여 답을 도출해 낼 수 있다. 로직 자체는 똑같기 때문에 3차원 리스트로 입력받고 잘 처리하기만 하면 쉽게 풀 수 있는 문제였다. 하지만 3차원 리스트를 입력받고 다루는데 익숙치 않아 조금 시간이 걸렸던 것 같다. 7576번 7579번 1 graph: 2차원 리스트 graph: 3차원 리스트 2 탐색 방향: 상하좌우(4개) 탐색 방향: 위, 아래, 왼쪽, 오른쪽, 앞, 뒤(6개) 2) 소스코드 from collections import deque # 가로, 세로, 높이 m, n, h = map(int, input().split()) # 0: 안익음, 1: ..
[백준] 7576번 - 토마토 풀이 시간: 40분 이내 1) 문제 해결 아이디어 토마토가 모두 익을 때까지 최소 날짜를 구하는 문제다. 익은 토마토가 상하좌우로 인접한 위치에 있는 익지 않은 토마토를 익힌다. 지금껏 풀어왔던 최단 경로 문제와 비슷하며 이 문제는 BFS로 풀어야 한다. 이 문제에서 3가지 케이스가 있다. 1. 저장될 때부터 모든 토마토가 익어있는 경우(즉, 입력받은 2차원 리스트에 0인 값이 없다면) -> 0 출력 2. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익지 못하는 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나라도 있으면) -> -1 출력 3. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익었을 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나도..
