전체 글

토마토 풀이

문제 링크: 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][..

섬의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/4963 백준 알고리즘 기초 2/2 600에서 6번째 - 4963번 섬의 개수를 풀어보았다. 풀이: https://aigong.tistory.com/513 를 참고했다. C++ Python import sys sys.setrecursionlimit(100000) def dfs(a,b,c,d): inp[a][b]=2 for i in range(8): na,nb=a+dx[i],b+dy[i] if 0

단지번호붙이기 풀이

문제 링크: https://www.acmicpc.net/problem/2667 백준 알고리즘 기초 2/2 600에서 5번째 - 2667번 단지번호붙이기를 풀어보았다. 풀이: https://ji-gwang.tistory.com/294 를 참고했다. C++ Python from collections import deque def bfs(g,a,b): q=deque() q.append([a,b]) g[a][b]=0 cnt=1 while q: x,y=q.popleft() g[x][y]=0 for i in range(4): nx=x+dx[i] ny=y+dy[i] if nx=len(g) or ny=len(g): continue if g[nx][ny]==1: g[nx][ny]=0 q.append([nx,ny]) cn..

이분 그래프 풀이

문제 링크: https://www.acmicpc.net/problem/1707 백준 알고리즘 기초 2/2 600에서 4번째 - 1707번 이분 그래프를 풀어보았다. 풀이: https://ji-gwang.tistory.com/293 를 참고했다. C++ Python import sys sys.setrecursionlimit(100000) def dfs(v,a): global res if res: return visit[v]=a for i in mat[v]: if not visit[i]: dfs(i,-a) elif visit[v]==visit[i]: res=True return k=int(input()) for _ in range(k): v,e=map(int,sys.stdin.readline().split(..

연결 요소의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/11724 백준 알고리즘 기초 2/2 600에서 3번째 - 11724번 연결 요소의 개수를 풀어보았다. 풀이: 재귀허용 범위를 넓혀주고, dfs로 탐색한다. https://yuna0125.tistory.com/66 를 참고했다. C++ Python import sys sys.setrecursionlimit(100000) def dfs(v): visit[v]=True for i in mat[v]: if not visit[i]: visit[i]=True dfs(i) n,m=map(int,input().split()) mat=[[] for i in range(n+1)] cnt=0 for i in range(m): a,b=map(int,sys..

DFS와 BFS 풀이

문제 링크: https://www.acmicpc.net/problem/1260 백준 알고리즘 기초 2/2 600에서 2번째 - 1260번 DFS와 BFS를 풀어보았다. 풀이: deque를 이용해 bfs를 구현했다. 코드는 https://ji-gwang.tistory.com/291 를 참고했다. C++ Python from collections import deque def dfs(v): dvisit[v]=True print(v,end=' ') for i in range(1,n+1): if not dvisit[i] and mat[v][i]: dfs(i) def bfs(v): q=deque([v]) bvisit[v]=True while q: v=q.popleft() print(v,end=' ') for i ..

ABCDE 풀이

문제 링크: https://www.acmicpc.net/problem/13023 백준 알고리즘 기초 2/2 600에서 1번째 - 13023번 ABCDE를 풀어보았다. 풀이: dfs를 이용해 깊이가 5인지를 보는 문제이다. C++ Python def dfs(depth,idx): global res if depth==4: res=True return for i in connect[idx]: if not visit[i]: visit[i]=True dfs(depth+1,i) visit[i]=False n,m=map(int,input().split()) connect=[[] for i in range(n)] visit=[False]*n res=False for i in range(m): a,b=map(int,in..