https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net import sys from collections import deque m, n = map(int,sys.stdin.readline().split()) # 토마토를 담을 상자이다. box = [] # 정답을 구할때 사용할 수이다. count = 0 # 익은 토마토를 담을 리스트이다. hot_tomato = deque() # for 문을 돌리면서 박스를 토마토로 채운다. for i..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net from collections import deque n, m = map(int, input().split()) walk = 0 def bfs(x,y): queue = deque() queue.append((x,y)) dx = [-1,1,0,0] dy = [0,0,-1,1] while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if ..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net import sys sys.setrecursionlimit(10**6) T = int(input()) def dfs(x,y): if x>=m or x=n or y

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net n= int(input()) graph = [] for i in range(n): graph.append(list(map(int,input()))) visit = [[0]*n for i in range(n)] post = [] cnt = 0 def dfs(x,y): global cnt if x=n or y =n or graph[x][y] == 0: return False graph[..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net from collections import deque n = int(input()) m = int(input()) graph = [[0]*(n+1) for i in range(n+1)] visit = [0]*(n+1) for i in range(m): line = list(map(int,input().split())) graph[line[1]][line[0]] =1 graph[line[0]][line[..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque n, m, v = map(int, input().split()) graph = [[0 for i in range(n + 1)] for j in range(n + 1)] visit_d = [0] * (n + 1) visit_b = [0] * (n + 1) for i in range(m): line = list..

BFS "너비 우선 탐색" 알고리즘은 쉽게 말해 가까운 노드부터 탐색하는 알고리즘 DFS는 최대한 멀리, BFS 는 그 반대다. BFS의 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행라게 된다. 1) 탐색 시작 노드를 큐에 삽입하고 방문처리한다. 2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3) 2)번의 과정을 더이상 수행할 수 없을 때 까지 반복한다. from collections import deque # BFS 함수 정의 def bfs(graph, start, visited):..

DFS 깊이 우선 탐색 알고리즘 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘 1) 탐색 시작 노드를DFS 깊이 우선 탐색 알고리즘 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 "방문 처리"한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3) 2) 번의 과정을 더이상 수행할 수 없을 때까지 반복한다." 여기서 "방문처리" 는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되..