[백준] 1303번 - 전쟁 - 전투 풀이 시간: 15~20분 이내 정석대로만 풀면 아주 쉽게 풀 수 있는 문제로 DFS, BFS 풀이가 모두 가능하다. DFS 풀이가 시간, 메모리 효율이 더 뛰어나다. (풀이1) BFS 1) 문제 해결 아이디어 2) 소스코드 from collections import deque # BFS def bfs(x, y, color): cnt = 0 # 병사 수 queue = deque() # 시작 지점 삽입, 방문 처리 queue.append((x, y)) graph[x][y] = 0 while queue: x, y = queue.popleft() cnt += 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if(0
[백준] 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() # 시작 지점 삽입, ..
[백준] 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를 넣어주려고 했다. 그리고 마지막..
[백준] 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..
[이코테] 문제2 - 미로 탈출(152p) 풀이 시간: 40~45분 이내 1) 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상하좌우로 연결된 모드 노드의 길이가 1로 동일하므로 (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능함 1. 종료 조건 설정 항상 출구값을 리턴하기 때문에 종료 조건이 없어도 결과는 똑같다. 다만 종료 조건을 넣어주면 해당 좌표가 출구지점이 될 떄 까지만 탐색을 진행한다. 2. 탐색 조건에서 시작점 제외 상하좌우 탐색 시, 시작점은 갔던 곳이므로 탐색하지 않도록 조건을 설정하였다. 책의 코드처럼 시작점일 때도 탐색하게 해도 결과값은 달라지지 않지만 값이 3으로 덮어쓰여지게 된다. 1. 시작..
[이코테] 문제1 - 음료수 얼려 먹기 풀이 시간: 30분 이내 1) 문제 해결 아이디어 이 문제는 DFS 혹은 BFS로 해결 가능하다. 특정 지점에서 DFS/BFS를 수행하여 이동 가능한 모든 지점에 대해 방문 처리를 한다. dfs 문제는 재귀 함수를 이용하여 해결한다. 재귀 함수의 종료 조건은 해당 좌표가 범위를 벗어났을 경우다. 현재 좌표를 아직 방문하지 않았다면 방문 처리를 하고 상하좌우에 해당하는 좌표를 매개변수로 하여 dfs를 호출한다. 1. 해당 지점이 아직 방문하지 않은 곳이라면 방문 처리 2. 상하좌우 지점 재귀 호출로 탐색 2) 소스코드 n, m = map(int, input().split()) # 세로, 가로 graph = [list(map(int, input())) for _ in ..
