[백준] 2206번 - 벽 부수고 이동하기 풀이 시간: 1) 문제 해결 아이디어 언제 벽을 부숴야 할지 조건을 떠올리는게 쉽지 않았다. 최근에 푼 BFS 문제 중에는 난이도가 가장 높은 문제인 것 같다. 여러가지 아이디어를 떠올려보고 시도해봤으나 잘 되지 않고 시간이 너무 지체되서 풀이를 봤는데도 한 번에 이해가가지 않아 복습이 필요한 문제다. Q. visited 3차원 배열 생성 시 초기화하는 이유는? visited를 생성하는 부분에서 시작 좌표(0, 0)에 해당하는 부분을 1로 초기화해야한다. 그렇지 않으면 (0,1)이나 (1,0)의 인접좌표를 검사할 때 (0, 0)의 graph값이 0이므로 검사를 진행하게 되는 문제가 발생한다. 사실상 정답에 영향을 미치지는 않지만 헷갈리니 그냥 다 초기화하는 걸로..
[백준] 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: ..
[백준] 2178번 - 미로 탐색 풀이 시간: 30~40분 이내 1) 문제 해결 아이디어 이 문제는 시작 위치(1, 1)에서 도착 위치(N, M)으로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제다. 즉, 최단 경로를 구하는 문제로 BFS로 풀 수 있는 대표적인 문제이다. BFS로 문제를 풀어야 한다는 것은 알았으나 방문 처리를 할 때 기록해야하는 값을 전역변수로 변경, 대입하여 약간의 어려움을 겪었다. 첫번째 오류. 최소 이동 칸 수를 구하기 위해 전역변수를 쓴 것 처음에 이동 칸 수를 나타낼 전역변수(res)를 선언하고 popleft()할 때마다 res 값을 1 증가했다. 상하좌우를 탐색할 때 갈 수 있는 칸이면 큐에 삽입하고 방문처리를 하는데 칸의 값을 res를 넣어주려고 했다. 그리고 마지막..
[백준] 1012번 - 유기농 배추 풀이 시간: 30분 이내 이 문제는 DFS, BFS 2가지 방식으로 모두 풀 수 있는 문제다. 최대 재귀한도 깊이 문제로 BFS로 풀이하는 것이 더 좋을 듯 하다. (풀이1) BFS 1) 문제 해결 아이디어 2) 소스코드 from collections import deque # 위치벡터(상하좌우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS def bfs(x, y): # 시작 좌표 삽입, 방문처리 queue = deque() queue.append((x, y)) graph[x][y] = 0 while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[..
[백준] 2606번 - 바이러스 풀이 시간: 10분 이내 (풀이1) BFS 이용 이 문제는 노드 1이 포함된 그래프에서 1을 제외한 노드의 수를 구하는 문제다. 해당 문제는 입력받은 간선 정보를 통해 그래프(2차원 리스트)를 만들고 DFS/BFS로 문제를 풀 수 있다. 1) 문제 해결 아이디어 아래 코드는 BFS로 구현한 방법이다. 2) 소스코드 from collections import deque n = int(input()) # 컴퓨터 수 m = int(input()) # 컴퓨터 간선 수 graph = [[] for _ in range(n + 1)] visited = [False] * (n + 1) res = 0 # 1이 감염시킨 컴퓨터 수 for i in range(m): a, b = map(int..
