분류 전체보기

숨바꼭질 4 풀이

문제 링크: https://www.acmicpc.net/problem/13913 백준 알고리즘 기초 2/2 610에서 2번째 - 13913번 숨바꼭질 4를 풀어보았다. 풀이: https://velog.io/@ms269/%EB%B0%B1%EC%A4%80-13913-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-4-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python 를 참고했다. C++ Python from collections import deque def path(a): arr=[] tmp=a for i in range(visited[a]+1): arr.append(tmp) tmp=course[tmp] return arr[::-1] def bfs(a): q=deque([a]..

숨바꼭질 풀이

문제 링크: https://www.acmicpc.net/problem/1697 백준 알고리즘 기초 2/2 610에서 1번째 - 1697번 숨바꼭질을 풀어보았다. 풀이: https://letalearns.tistory.com/34 C++ Python from collections import deque def bfs(a): q=deque([a]) while q: b=q.popleft() if b==k: return visited[b] for i in (b-1,b+1,2*b): if 0

다리 만들기 풀이

문제 링크: https://www.acmicpc.net/problem/2146 백준 알고리즘 기초 2/2 602에서 3번째 - 2146번 다리 만들기를 풀어보았다. 풀이: https://velog.io/@thguss/%EB%B0%B1%EC%A4%80-2146.-%EB%8B%A4%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0-with.-Python 를 참고했다. C++ Python from collections import deque def island(a,b): q=deque() q.append([a,b]) while q: x,y=q.popleft() for (h,w) in [[1,0],[0,1],[-1,0],[0,-1]]: dx,dy=x+h,y+w if 0

DFS 스페셜 저지 풀이

문제 링크: https://www.acmicpc.net/problem/16964 백준 알고리즘 기초 2/2 602에서 2번째 - 16964번 DFS 스페셜 저지를 풀어보았다. 풀이: https://vixxcode.tistory.com/29 C++ Python import sys N = int(sys.stdin.readline()) graph=[[] for _ in range(N+1)] for _ in range(N-1): a,b=map(int,sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) ans= list(map(int,sys.stdin.readline().split())) level=[False]*(N+1) tsize = [0]..

BFS 스페셜 저지 풀이

문제 링크: https://www.acmicpc.net/problem/16940 백준 알고리즘 기초 2/2 602에서 1번째 - 16940번 BFS 스페셜 저지를 풀어보았다. 풀이: https://dallae7.tistory.com/133 C++ Python import sys from collections import deque input=sys.stdin.readline def bfs(s): visited=[False]*(n+1) q=deque() q.append(s) ret=[1] visited[s]=True while q: start = q.popleft() for node in graph[start]: if not visited[node]: q.append(node) visited[node]=T..

서울 지하철 2호선 풀이

문제 링크: https://www.acmicpc.net/problem/16947 백준 알고리즘 기초 2/2 601에서 2번째 - 16947번 서울 지하철 2호선을 풀어보았다. 풀이: https://baby-ohgu.tistory.com/35 C++ Python import sys from collections import deque sys.setrecursionlimit(10**9) def dfs(x, cnt): if check[x]: if cnt - dist[x] >= 3: return x else: return -1 check[x] = 1 dist[x] = cnt for y in adj_list[x]: cycleStartNode = dfs(y, cnt + 1) if cycleStartNode != -..

Two Dots 풀이

문제 링크: https://www.acmicpc.net/problem/16929 백준 알고리즘 기초 2/2 601에서 1번째 - 16929번 Two Dots를 풀어보았다. 풀이: https://chelseashin.tistory.com/83 를 참고했다. C++ Python def dfs(a,b,c,d,e): dx=(1,0,-1,0) dy=(0,1,0,-1) if visit[a][b]: print("Yes") exit() visit[a][b]=True for i in range(4): nx=a+dx[i] ny=b+dy[i] if not (0

나이트의 이동 풀이

문제 링크: https://www.acmicpc.net/problem/7562 백준 알고리즘 기초 2/2 600에서 9번째 - 7562번 나이트의 이동을 풀어보았다. 풀이: bfs를 쓰는 문제이다. C++ Python from collections import deque def bfs(a,b,c,d): dx=[-1,1,2,2,1,-1,-2,-2] dy=[2,2,1,-1,-2,-2,-1,1] queue=deque() queue.append((a,b)) while queue: x,y=queue.popleft() if x==c and y==d: return graph[x][y]-1 for i in range(8): nx=x+dx[i] ny=y+dy[i] if 0

토마토 풀이

문제 링크: https://www.acmicpc.net/problem/7576 백준 알고리즘 기초 2/2 600에서 8번째 - 7576번 토마토를 풀어보았다. 풀이: https://jiwon-coding.tistory.com/97 를 참고했다. C++ Python from collections import deque def bfs(): dx=[-1,1,0,0] dy=[0,0,-1,1] queue=deque([]) for i in range(n): for j in range(m): if graph[i][j]==1: queue.append([i,j]) while queue: x,y=queue.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] if 0

미로 탐색 풀이

문제 링크: https://www.acmicpc.net/problem/2178 백준 알고리즘 기초 2/2 600에서 7번째 - 2178번 미로 탐색을 풀어보았다. 풀이: https://jokerldg.github.io/algorithm/2021/03/24/maze.html 를 참고해 bfs를 썼다. C++ Python from collections import deque def bfs(a,b): dx=[-1,1,0,0] dy=[0,0,-1,1] queue=deque() queue.append((a,b)) while queue: a,b=queue.popleft() for i in range(4): na=a+dx[i] nb=b+dy[i] if na=n or nb=m: continue if graph[na][..