Simple Explain

#11403 경로찾기 https://www.acmicpc.net/problem/11403  너무 어렵게 생각했다.bfs를 여러번 돌리면 되는데,뭔가 한 번의 함수 실행으로 완벽하게 해결하고 싶어서 더 고민을 했다.  하하하하하하 n = int(input())links = [[int(x) for x in input().split()] for __ in range(n)]# bfsanswer = [[0 for _ in range(n)] for __ in range(n)]def bfs(start): # print(start) q = [start] visited = [0 for _ in range(n)] while q: prev = q.pop(0) for i in r..

#21736 헌내기는 친구가 필요해 (https://www.acmicpc.net/problem/21736)  유난히 바쁜 날이라만만해보이는 문제로 (class 4 중) 빠르게 풀었다. n, m = map(int, input().split())campus = []visited = []q = []for i in range(n): row = [x for x in input()] v = [False for _ in range(m)] for j in range(m): # O는 빈 공간, X는 벽, I는 도연이, P는 사람이다 if row[j] == "I": q.append([i, j]) v[j] = True elif ro..

#7569 토마토 (https://www.acmicpc.net/problem/7569) 오랜만에 풀어낸 BFS문제였다. from sys import stdinfrom collections import dequeinput = stdin.readline# 쌓아올려지는 상자의 수를 나타내는 H# M은 상자의 가로 칸의 수# N은 상자의 세로 칸의 수를 나타낸다# 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다m, n, h = map(int, input().split())tomato = [] # 토마토 상자 데이터red = deque() # 익은 토마토 데이터# 방문 기록visited = [[[-1 for _ in range(m)] for __ in range(n)] for _..

#14940 쉬운 최단거리 (https://www.acmicpc.net/problem/14940)  자꾸 이것저것 조건 빼먹어서 은근히 귀찮았던 문제였다. 단순 BFS로 풀이했다.다만 시작 지점이 입력마다 달라질 수 있음을 유의해야하며벽에 가로막혀 도달할 수 없는 지점은 -1로 표기하는 것이 주의해야할 지점이다. h, w = map(int, input().split())maps = []t = []# points = []for r in range(h): tmp = list(map(int, input().split())) for c in range(w): if tmp[c] == 2: # target check t.append([r, c]) tm..

#1389번 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 확실히 문제가 안풀리는 날에는 문제 이해를 제대로 안한 경우가 많아서 속상하다. 신중에 신중을 기하는 내가 되길 바란다. 내 코드 from collections import deque N, M = map(int, input().split()) network = [[] for _ in range(N+1)] for..

#16953번 A -> B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A 라는 수를 1. 2를 곱한다 2. 1을 수의 오른쪽에 추가한다 라는 두 가지 연산을 이용해서 B라는 수로 만들 때, 연산횟수를 출력하면 된다. 처음에는 DP라고 생각했었는데, 알고보니 BFS였다. (아마 연산의 종류가 두 가지이기 때문이 아닐까..?) 틀린코드 from collections import deque A, B = map(int, input().split()) visited = [False]*(B+1) que = deque() que.append(A) visited[A] = 1 w..

#14502번 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 잘 풀었다. import sys input = sys.stdin.readline N, M = map(int, input().split()) maps = [] viruses = [] walls = [] zeros = [] for i in range(N): tmp = list(map(int, input().split())) for j in range(M): if tmp[j] == 1: wal..

#9019번 DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 최소 연산 횟수 (최단거리 등) 은 무조건 BFS! 바로 짰다! 시간초과 코드 def cal_d(num): return num*2 % 10000 def cal_s(num): num -= 1 if num X라고 할 때 2) que 저장 위 과정을 S R L 모두 반복 이후 X 앞에 있는 모든 que 해결 1) X 호출 2) 정답여부 확인 이렇게 진행된다. 때문에 q..

저번 포스팅 중에서 0-1 BFS를 공부할 필요가 있다고 했었다. 근데 오늘 자연스럽게 해버림 #1261 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 처음엔 그냥 DP를 사용한 BFS로 풀이했다. N, M = map(int, input().split()) way = [[int(x) for x in input()] for _ in range(M)] visited = [[-1 for _ in range(N)] fo..

#13023번 ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 처음에는 모든 노드가 다음 단계 노드로 연결될 수 있음을 검증하는거라 생각했다. 그래서 엄청 열심히 풀었는데 Recursion Error나와서 진짜 짜증났다... 그래서 검색했더니 그냥 깊이가 4인 노트 찾는거란다....... ABCDE이래서 되게 헷갈렸던.. 백준의 단점이라 하면 부족한 설명이 아닌가 싶다. from operator import ne import sys N, M = map(int, input().split()) graph = [[] for _ in range(..