코딩,안되면 될때까지

백준 1012번 파이썬풀이 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net -DFS알고리즘(재귀함수)사용!!!! 배추가 심어져있는곳은 1 심어져 있지 않은곳은 0이다. 그래프를 돌면서 배추가 심어져있는곳에서 DFS알고리즘을 적용한다. 해당위치에서 DFS알고리즘이 종료될때마다 count+=1을 해준다. -DFS알고리즘 설명- 배추가 심어져 있는곳에서 상,하,좌,우 네가지 방향을 살핀다. 만약 네가지 방향중 배추가 심어져 있고 아직 방문하지 않은 경우(grap..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1.각 컴퓨터의 방문여부를 저장하는 배열(visited)을 선언한다. 2.-DFS풀이법- 2-1. 1번에서 출발하므로 visited[1]에 방문을 체크한다. 2-2. 1번과 연결되어있는 컴퓨터로 이동해 방문 여부를 확인한다. 2-3. 방문하지 않은 경우 바이러스를 확산시키고(count+=1) DFS 함수를 재귀적으로 호출한다. 2-4. 연결되어 있는 노드가 이미 방문이 된경우 연결되어있는 다른 노드로 ..

백준 18405번 파이썬 풀이 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 바이러스의 정보를 담을 리스트(data)에 바이러스의 종류,위치,시간을 입력한다. 바이러스는 항상 낮은번호부터 확산한다 했으므로 data를 오름차순 정렬한다. data를 큐에 넣은후 BFS알고리즘을 적용한다. -BFS알고리즘 설명- 1. 시간(s)가 목표한 시간(target_s)에 도달하면 while문을 멈춘다. 2. 큐에서 원소를 꺼낸..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1.울타리 설치가 가능한 모든 경우의 수를 탐색한다.(DFS알고리즘 사용) 2.각각의 경우에서 안전영역의 크기를 계산해 최댓값을 구한다. 3.안전영역의 크기를 구하는 과정 울타리 설치가 가능한 모든 경우의 수만큼 울타리를 설치한다.(dfs메서드) 울타리가 설치된 상태에서 바이러스가 퍼져나갈 수 있는 가장 넓은 영역만큼 바이러스를 퍼뜨린다.(virus함수) 바이러스가 퍼진 상태에서의 안전영역의 넓이를 resul..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net -BFS알고리즘사용!! 그래프에서 집이 있는곳의 방문여부를 저장할 visited 배열을 선언한다.(초기값은 전부 미방문,즉 False로 선언) 집이 있는곳에서 출발해 인접한 네 방향의 위치를 확인한다. 이때 그래프의 값이 1인곳이면서(즉 집이 있는곳)동시에 아직 방문하지 않은경우 해당위치를 queue에 삽입한다. 그리고 단지의 크기를 저장할 total(초기값=1)변수에 1을 더해준다. (※ 해당위치..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 시작위치를 queue에 삽입한다. distance배열(시작위치에서 각 노드까지의 거리를 저장하는 배열)을 선언한다. distance배열에서 시작위치에 해당하는 인덱스의 값을 0으로 설정한다. queue에서 원소를 추출한다음 각 인접노드를 queue에 삽입한다. distance배열에서 각 노드에 해당하는 인덱스의 값을 갱신한다..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net -BFS알고리즘 사용 출발위치를 queue에 넣는다. queue에 넣은 원소를 추출한다음 해당원소의 인접노드중 이동가능한 노드를 queue에 넣는다. 이동가능한 노드를 queue에 삽입하고 이동거리를 +1해준다. 위의 2,3번째 과정을 queue가 빌때까지 계속 반복해준다. from collections import deque n,m = map(int,input().split()) dx = [-1,1,0,0] dy = [0,0,..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net https://hae-sooo97.tistory.com/25 탐색(DFS/BFS) 1)DFS :Depth-First Search, 깊이우선탐색,그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 탐색 시작노드를 스택에 삽입하고 방문처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접노드가 hae-sooo97.tistory.com ※주의점 : dfs함수를 호출..