[백준] 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() # 시작 지점 삽입, ..
[백준] 14503번 - 로봇 청소기 풀이 시간: (풀이1) BFS 이용 1) 문제 해결 아이디어 예전에 이와 거의 비슷한 문제를 푼 적이 있으니 아래글을 참고하자. [참고] https://hseungyeon.tistory.com/180 [구현] 문제5 - 게임 개발 게임 개발 1) 문제 해결 아이디어 전형적인 시뮬레이션 문제 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 좋음 2차원 리스트 선언시 리스 hseungyeon.tistory.com 첫번째 오류. c, d 조건을 검사하는 경우의 설정 오류 c, d 조건은 4번 회전을 했을경우 검사해야한다. 처음엔 a 조건을 한번이라도 만족하면 break를 하기 때문에 break되지 않고 for문이 끝나면 ..
[백준] 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..
