BFS

문제 요약도연이는 캠퍼스에서 만날 수 있는 친구의 수를 알고 싶어한다. 캠퍼스는 ( N \times M ) 크기이며, 도연이는 빈 공간('O')과 사람('P')이 있는 곳으로 이동할 수 있다. 벽('X')은 이동할 수 없다. 도연이가 시작하는 위치는 'I'로 주어진다. 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성하는 문제이다.입력첫 번째 줄에 캠퍼스의 크기를 나타내는 두 정수 ( N )과 ( M )이 주어진다.다음 ( N )개의 줄에 캠퍼스의 정보가 주어진다. 'O'는 빈 공간, 'X'는 벽, 'I'는 도연이의 시작 위치, 'P'는 사람이다.출력도연이가 만날 수 있는 사람의 수를 출력한다. 만약 아무도 만나지 못한 경우 "TT"를 출력한다.  풀이 설명이 문제는 BFS(너비 우선 탐색)를..

문제 요약지도에서 각 지점에 대해 목표 지점(값이 2인 지점)까지의 거리를 구하는 문제이다. 지도는 가로와 세로로만 움직일 수 있으며, 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표 지점을 의미한다. 풀이 설명이 문제는 너비 우선 탐색(BFS)를 사용하여 각 지점에서 목표 지점까지의 최단 거리를 구하는 문제이다.BFS는 최단 거리를 구하는 데 적합한 알고리즘이다. from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [list(map(int, input().split())) for _ in range(n)]def bfs(graph, n, m): distan..

문제 요약보드 게임에서 플레이어는 주사위를 굴려 1번 칸에서 100번 칸까지 이동해야 한다.사다리는 도착하면 더 높은 번호로 이동하고, 뱀은 더 낮은 번호로 이동하게 한다.100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 구한다. 풀이from collections import dequeimport sysinput = sys.stdin.readlinedef snakes_and_ladders(N, M, ladders, snakes): board = list(range(101)) # 보드의 각 칸 초기화 for start, end in ladders.items(): board[start] = end # 사다리 설정 for start, end in snakes.it..

문제 요약네 개의 명령어 D, S, L, R 가 있는 계산기두 정수 A, B가 주어졌을 때, A를 B로 바꾸는 최소한의 명령어 생성-> BFSBFS라는 건 어렵지 않게 생각해낼 수 있었는데.. 이 문제에서 가장 어려웠던 점은 시간 초과였다. 시간 초과 풀이from collections import dequedef D(n): return (2 * n) % 10000def S(n): return n - 1 if n != 0 else 9999def L(n): n = f"{n:04}" # 네 자릿수로 맞추기 return int(n[1:] + n[0])def R(n): n = f"{n:04}" # 네 자릿수로 맞추기 return int(n[-1] + n[:-1])def bfs(..

풀이 1: 플로이드-워셜플로이드-워셜: 모든 정점 쌍 최단 거리 계산시간 복잡도는 O(N^3) - 이 문제는 N 최댓값 100이므로 이 문제에서 사용할 수 있다.import sysinput = sys.stdin.readlineN, M = map(int, input().split())# 거리 배열 초기화INF = sys.maxsizedist = [[INF] * (N+1) for _ in range(N+1)]# 자신과의 거리는 0으로for i in range(1, N+1): dist[i][i] = 0# 친구 관계 입력for _ in range(M): A, B = map(int, input().split()) dist[A][B] = 1 dist[B][A] = 1# 플로이드-워셜for k ..

방향 없는 그래프 주어짐 -> 연결 요소(connected component) 개수 구하는 프로그램 아이디어그래프 탐색 (DFS/BFS)방문 못한 노드 하나라도 있다면 카운트 증가하고그 방문 못한 노드 (false 노드)에서 시작해서 다시 그래프 탐색false 노드 없을 때까지 그래프 탐색 반복 풀이 - DFS 사용import sysinput = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for _ in range(M): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u)visited = [False] * (N+..

문제 요약수빈 현재 위치 N, 동생 현재 위치 K, 0부터 100,000 까지의 정수수빈이가 동생을 찾을 수 있는 가장 빠른 시간 구하기.수빈이가 이동할 수 있는 건 3가지 : X-1, X+1, 2*X 풀이시작 노드에 연결된 노드는 3개, 각 노드에서 1초가 지날 때마다 하나씩 이동하다가,목표 노드에 도착하면 걸린 시간 리턴-> BFS로 풀이할 수 있다 def bfs(n, k): if n == k: # 같다면 걸린 시간 0 return 0 visited = [False] * 100001 # 입력 값 범위보다 크게 queue = deque([(n, 0)]) # n에는 현재 노드 위치, 0에는 걸린 시간 저장 while queue: cur, time = queu..

문제 요약n * m 사이즈 토마토 보관 상자익은 토마토 인접한 곳에 있는 건 영향 받아 익게 됨.창고에 보관한 토마토들이 최소 며칠 지나면 다 익게 되는지!단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. M,N은 2부터 10001은 익은 토마토, 0은 안 익은 토마토, -1은 토마토 없음토마토는 최소 하나 있다고 한다. 모두 익을 때까지의 최소 날짜를 출력하되,모든 토마토가 익어있다면 0 출력, 모두 익지 못하는 상황이라면 -1을 출력한다.  풀이이 문제는 BFS로 풀어야 하는 문제다. 하루가 지날 때마다 영향을 받아 익게 되기 때문. from collections import dequem, n = map(int, input().split()) # 가로, 세로graph = []for i in..

풀이 1: DFS, 재귀이용 - RecursionErrordef dfs(x, y): visited[x][y] = True for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny = x + dx, y + dy if 0 첫번째 풀이이다. DFS와 재귀를 사용하여 풀었더니 Recursion Error가 났다.Recursion Error: 재귀와 관련된 에러. 주로 Python이 정한 최대 재귀 깊이보다 더 깊어질 때.이 경우, 재귀를 사용하지 않도록 바꾸어야 한다.BFS를 사용해서 풀거나, 재귀 없이 DFS를 구현해야 한다. 참고 링크 : https://yesolz.tistory.com/entry/Python-%EB%B0%B1%EC%A..

1. n, m, v 입력 받기 (띄어쓰기 입력)n, m, v = map(int, input().split())N(정점수), M(간선수), V(탐색 시작할 정점 번호) 2. 그래프 입력 받기 (노드 연결 정보) - 인접 행렬graph = [[0] * (n+1) for _ in range(n+1)]for i in range(m): a, b = map(int, input().split()) graph[a][b] = graph[b][a] = 1 정점 번호와 인덱스 일치시키기 위해 n+1로 초기화무방향 그래프이므로 graph[a][b] = graph[b][a] = 1 ** 그래프 출력하기def print_graph(graph): for row in graph[1:]: # 0번째 행과 열은 사용하..