[백준] 5014번 - 스타트링크 풀이 시간: 15분 이내 이 문제는 S층에서 G층으로 가기 위해 눌러야 하는 최소 버튼 수를 구하는 것으로 최단경로 문제에 속하므로 BFS로 풀어야 한다. 이전에 풀었던 문제와 거의 유사하므로 참고하면 좋을 듯 하다. https://hseungyeon.tistory.com/224 [DFS/BFS/완전탐색] ▲ 16953번 - A → B(BFS) [백준] 16953번 - A → B 풀이 시간: 40분이내 1) 문제 해결 아이디어 리플릿에서 코드를 짜고 실행을 했을 때는 graph크기를 (10**9 _+ 1) 로 생성하니 그냥 종료 되었다. 크기를 수정하니 전혀 문제가 hseungyeon.tistory.com 방문처리를 하는 방법에 따라 2가지 방식으로 풀 수 있다. (풀이..
[백준] 2468번 - 안전 영역 풀이 시간: 90분 이내 문제를 푸는 데는 20분 정도 걸렸는데 오류를 해결하는데 시간이 오래걸렸다. 나중에 다시한번 풀어봐야할 문제인 것 같다. (풀이1) BFS 1) 문제 해결 아이디어 첫번째 오류. TypeError 예약어를 변수명으로 사용하였기 때문에 나타난 오류다. 변수명을 min, max와 같은 예약어를 사용하면 문제가 된다! [참고] https://m.blog.naver.com/passionisall/221828106961 [Python] 파이썬 'int' object is not callable 에러코드 설명 atom 편집기의 경우 한 파일에서 이전에 쓰던 코드를 지우고 새로 작성할 경우 문제가 없을 수 있다. 하지... blog.naver.com 두번째 ..
[백준] 1743번 - 음식물 피하기 풀이 시간: 10분 이내 (풀이1) BFS 이용 1) 문제 해결 아이디어 BFS를 이용하여 문제를 해결하였다. popleft()를 할 때마다 인접한 음식물의 크기(res)를 1씩 카운팅하여 상하좌우에 인접한 음식물이 없을 때까지 이를 반복하고 종료시 음식물 크기(res)를 반환한다. for문을 돌려 graph에서 음식물(1)을 발견할 때마다 해당 좌표를 시작지점으로 하여 bfs()를 호출하였고 반환 값을 음식물 크기를 저장하는 리스트(size)에 하나씩 삽입하여 최댓값을 출력하였다. 2) 소스코드 from collections import deque # BFS def bfs(x, y): res = 0 # 음식물 크기 queue = deque() # 시작 지점 삽입, ..
[백준] 16953번 - A → B 풀이 시간: 40분이내 1) 문제 해결 아이디어 리플릿에서 코드를 짜고 실행을 했을 때는 graph크기를 (10**9 _+ 1) 로 생성하니 그냥 종료 되었다. 크기를 수정하니 전혀 문제가 없었으나 제출할 때 메모리 초과 오류가 생겼다. 코드를 짜는 것은 쉬웠는데 오류를 고치는데 시간이 많이 걸렸다. 모든 BFS 문제는 graph를 만들어서 문제를 푼다는 고정관념때문에 틀린 문제였다. 항상 graph를 만들어 문제를 풀다보니 자연스레 또 그래프를 만들 생각만 했던 것 같다. BFS를 풀기 위해서는 큐만 있으면 된다!! 1. 큐 생성 및 (시작값, 누적 연산횟수) 형태로 삽입 2. 2가지 연산 수행 2-1. 큐에서 하나 꺼내기 2-2. 2가지 연산한 결과값(nx)이 1보..
[백준] 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,..
[백준] 2178번 - 미로 탐색 풀이 시간: 30~40분 이내 1) 문제 해결 아이디어 이 문제는 시작 위치(1, 1)에서 도착 위치(N, M)으로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제다. 즉, 최단 경로를 구하는 문제로 BFS로 풀 수 있는 대표적인 문제이다. BFS로 문제를 풀어야 한다는 것은 알았으나 방문 처리를 할 때 기록해야하는 값을 전역변수로 변경, 대입하여 약간의 어려움을 겪었다. 첫번째 오류. 최소 이동 칸 수를 구하기 위해 전역변수를 쓴 것 처음에 이동 칸 수를 나타낼 전역변수(res)를 선언하고 popleft()할 때마다 res 값을 1 증가했다. 상하좌우를 탐색할 때 갈 수 있는 칸이면 큐에 삽입하고 방문처리를 하는데 칸의 값을 res를 넣어주려고 했다. 그리고 마지막..
