본문 바로가기
반응형

백준알고리즘/DFS 와 BFS31

(Python/🥈1)백준 알고리즘 2667번: 단지번호붙이기 문제출처: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이: 틀린코드 import sys from collections import deque N = int(input()) def bfs(x,y): count = 0 queue =deque([(x,y)]) while queue: a, b = queue.popleft() for next_x, next_y in move: nx ,ny = a + next_x, b + next_y if N > nx.. 2023. 2. 16.
(Python/🥈2)백준 알고리즘 11724번: 연결 요소의 개수 문제 출처: https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이: import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline N, M = map(int,input().split(" ")) board = [[] for _ in range(N+1)] visited = [False]* ( N + 1 ) for i in rang.. 2023. 2. 14.
(Python/🥈2)백준 알고리즘 1012번: 유기농 배추 문제 출처: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이: import sys from collections import deque T = int(input()) move = [(0,1),(0,-1),(1,0),(-1,0)] # 가로 세로 K갯수 def bfs(a,b): Q = deque([(a,b)]) visited[a][b] = 0 # 1을 0 으로 방문했음 while Q: x,y = Q.popleft() for sx, sy in move: d.. 2023. 2. 14.
(Python/🥈1)백준 알고리즘 1697번: 숨바꼭질 문제 출처: https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이: import sys from collections import deque sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r') def bfs(v): Q = deque([N]) while Q: v = Q.popleft() if v == M : return visited[v] for next_.. 2023. 2. 13.
(Python/🥈1)백준 알고리즘 2178번: 미로탐색 문제출처: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이: import sys from collections import deque sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r') N, M = map(int,input().split(" ")) map = [list(map(int,input())) for i in range(N)] visited = [ [-1] * (M) for i in range(N)].. 2023. 2. 13.
(Python/🥈2)백준 알고리즘 1260번: DFS 와 BFS 문제출처: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이: import sys from collections import deque sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r') def bfs(v): queue = deque([v]) visited[v] = True while queue: q = queue.popleft() prin.. 2023. 2. 13.
반응형

티스토리툴바