공작소

문제 링크 : https://www.acmicpc.net/problem/1697풀이 과정수빈이의 위치를 정점으로, 3개의 이동하는 방법을 간선으로 인식하여 너비 우선 탐색을 이용해 풀이했다. 전체 코드# 1697 : 숨바꼭질import sysfrom collections import dequeinput = sys.stdin.readlinen, k = map(int, input().rstrip().split())queue = deque()queue.append(n)visited = [False for _ in range(100001)]visited[n] = Truetime = 0done = Falsewhile queue: size = len(queue) for _ in range(size): ..

문제 링크 : https://www.acmicpc.net/problem/1463풀이 과정문제에서 나오는 연산 과정과, 연산을 하고난 뒤의 결과를 그래프로 인식하여 BFS로 풀이했다.탐색을 진행하는 도중 1이 나오면 바로 탐색을 종료하고 탐색 횟수를 출력한다.전체 코드# 1463 : 1로 만들기import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input().rstrip())visited = [False for _ in range(int(1e6)+1)]queue = deque()queue.append(n)visited[n] = Truetime = 0done = Falsewhile queue: size = len(queue)..

문제 링크 : https://www.acmicpc.net/problem/1260풀이 과정DFS와 BFS를 구현하여 실행 과정을 출력했다.전체 코드# 1260 : DFS와 BFSimport sysfrom collections import dequeinput = sys.stdin.readlinen, m, v = map(int, input().rstrip().split())edges = [[] for _ in range(n+1)]for _ in range(m): a, b = map(int, input().rstrip().split()) edges[a].append(b) edges[b].append(a)for i in range(1, n+1): edges[i].sort()# DFSans ..

문제 링크 : https://www.acmicpc.net/problem/1012풀이 과정BFS를 이용해 이웃한 배추 그룹의 개수를 센다.전체 코드# 1012 : 유기농 배추import sysfrom collections import dequeinput = sys.stdin.readlinet = int(input().rstrip())for _ in range(t): m, n, k = map(int, input().rstrip().split()) maps = [[False for _ in range(m)] for _ in range(n)] for _ in range(k): x, y = map(int, input().rstrip().split()) maps[y][x] ..

문제 링크 : https://www.acmicpc.net/problem/11724풀이 과정BFS 를 이용해 연결되있는 그룹들의 개수를 셌다.전체 코드# 11724 : 연결 요소의 개수import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())edges = [[] for _ in range(n+1)]for _ in range(m): u, v = map(int, input().rstrip().split()) edges[u].append(v) edges[v].append(u)visited = [False for _ in range(n+1)]cnt = 0for i i..

문제 링크 : https://www.acmicpc.net/problem/21736풀이 과정I 부터 시작하는 너비 우선 탐색을 이용해 방문하는 P 의 개수를 셌다.전체 코드# 21736 : 헌내기는 친구가 필요해import sysfrom collections import dequeinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())maps = [list(input().rstrip()) for _ in range(n)]queue = deque()visited = [[False for _ in range(m)] for _ in range(n)]for i in range(n): for j in range(m): if maps[..

문제 링크 : https://www.acmicpc.net/problem/9019첫 번째 풀이A에서 B로 바꾸는 최소한의 명령어를 구해야 하는 문제이다.D, S, L, R의 명령어를 사용하는 것을 그래프의 간선으로 인식하고 BFS (너비 우선 탐색) 을 사용하면 최소한의 명령어를 구할 수 있다.D, S, L, R 을 사용했을 때의 결과와 현재까지 사용한 명령어 현황을 저장해서 탐색했다. 아무 명령어나 출력해도 되기 때문에, 현재 상태가 B인 정점에 도달했다면 바로 사용한 명령어를 출력하고 종료한다.첫 번째 코드# 9019 : DSLRimport sysfrom collections import dequeinput = sys.stdin.readlinet = int(input().rstrip())for _ in..

문제 링크 : https://www.acmicpc.net/problem/7576풀이 과정익은 토마토 1을 시작으로, 너비 우선 탐색을 이용했다. 인접한 모든 토마토가 익는 날짜를 계산하면 된다.토마토의 전체 개수를 파악하여, 익지 않은 토마토가 존재하는지 여부 또한 파악해야 한다. 전체 코드# 7576 : 토마토import sysfrom collections import dequeinput = sys.stdin.readlinem, n = map(int, input().rstrip().split())arr = [list(map(int, input().rstrip().split())) for _ in range(n)]visited = [[False for _ in range(m)] for _ in range..