![]()
1. 문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2. 코드 n = int(input()) # 노드 개수 size = int(input()) # n번 노드에 연결된 노드 graph = [[] for _ in range(n+1)] # 방문한 노드는 1, 방문하지 않은 노드는 0 visited =[0]*(n+1) for i in range(size): a,b = map(int,input().split()) # 그래프 넣어주기 ~ graph[a]+=[b] graph[b]+=[a] def dfs(v): # 방문한..
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net Algorithm 1. 배열 A를 입력받을 때 상하좌우를 탐색하기 편하게 하기 위해 가장자리의 바깥부분에 1을 추가한다. 2. 선언된 A 중에서 A[i][j] == 0인 (i, j)에 대한 집합 Z를 생성한다. 3. A를 복사한 B에 대해 Z 중 3개를 골라 그 (i, j)에 해당하는 B의 값을 1로 바꾼다. 4. dfs로 상하좌우에 0인 부분을 찾아서 그 부분을 2로 바꿔가며 2로 바뀐 0의 개수 x를..
문제링크 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 코드 from collections import deque from copy import deepcopy def bfs_water(graph,water_idx): q = deque() for x,y in water_idx: q.append((x,y)) time[x][y] = 0 while q: x,y = q.popleft() for i in range(4): nx = x + dx[i] ny = y +..
![]()
풀이 각 정점에서 연결된 정점들을 번호순으로 처리하기 위해 정렬한다. DFS 함수에서는 현재 정점을 방문하고, 방문했다는 표시를 한 뒤, 현재 정점에 연결된 정점들을 재귀적으로 방문한다. BFS 탐색은 큐를 이용하여 구현한다. DFS 함수와 BFS 함수에서 visited 배열을 공유하지 않도록 주의하면서 구현하면 된다. 코드 #include #include #include #include using namespace std; vector graph[1001]; bool visited[1001]; void dfs(int node) { visited[node] = true; cout m >> v; for(int i = 0; i > a >> b; graph[a]..
![]()
https://www.acmicpc.net/problem/1520 문제 분석 난이도 골드 3 분류 그래프 탐색, 다이나믹 프로그래밍 + (DFS or 우선순위 큐) 문제 문제 풀이 풀이 맨 마지막 위치에서 인접한 부분의 자신보다 큰 수를 우선순위 큐에 넣어준다. 그러면 항상 앞에는 작은 수가 들어가고 그 순서대로 탐색하게 된다. 주변의 인접한 숫자들 중 자신보다 큰 수가 있다면 현재의 방문횟수를 더해주고, 방문한 적이 없는 곳이라면 우선순위 큐에 넣어준다. M*N은 최대 250000(500*500) 이고, push pop의 시간복잡도는 logN이므로 시간은 넉넉하다. 소스코드 from sys import stdin from heapq import heappop,heappush input=stdin.rea..
![]()
bfs와 dfs를 모두 함수로 구현해서 각각 한번씩 실행을 해줘야 한다. 각각 한 번씩만 하면 되므로 이를 기록할 리스트를 1개씩 만들어두고 입력받은 점에 대해서는 2차원 배열에 저장해두자 bfs와 dfs를 실행하면서 각각의 경우에 2차원 배열에 저장된 경로들을 참고하여 출력할 수 있는 경우들을 출력하고 출력 형식은 한 줄로 붙어있어야 하므로 그때그때 출력하고 end=" "를 통해서 한 줄로 출력하자. import sys from collections import deque def main(): N, M, V = map(int, sys.stdin.readline().split()) graph = [[False] * (N+1) for _ in range(N+1)] for _ in range(M): a, b..
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net CODE 처음 실패 import sys input = sys.stdin.readline n, k = map(int, input().split()) stack = [] number = list(input().rstrip()) for i in range(n): while k>0 and stack and stack[-1] < number[i]: stack.pop() k-=1 stack.append(number[i]) print(*stack,sep='') 두번째 성공 import ..
![]()
4963번: 섬의 개수 (acmicpc.net) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 소스코드 설명 sys.setrecursionlimit()를 이용해 재귀호출의 최대 깊이 증가 하나의 섬을 둘러싸고 있는 최대 8개의 섬이 존재하며 각 섬으로 이동 가능하므로 현재 섬의 좌표가 (0,0)일 때, 각 섬의 x좌표와 y좌표를 dx, dy 리스트로 생성 w, h을 입력받고 둘다 0이라면 while문 종료 현재 섬과 바다의 위치를 보여주는 2차 배열 a 생성 a와 똑같은 위치의 칸에 방문 여부를 알려주..
![]()
문제 https://www.acmicpc.net/problem/1124 1124번: 언더프라임 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, www.acmicpc.net Algorithm 자연수 X를 소인수분해를 하면 소수들의 곱이 되고, 소인수의 개수가 소수이면 자연수 X가 언더프라임이다. 범위를 입력받아 범위안에 있는 언더프라임의 개수를 찾는 문제이다. a와 b 사이가 최대 100000이고, 소인수분해하는데 루트100000정도 쓴다고 하면 31,622,776정도 나오므로 시간제한에 돌 수 있다고 생각해서 아래처럼 코드를 구성했다. 자연수의..
https://www.acmicpc.net/problem/1012 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추..
![]()
BFS와 최단 경로 BFS는 최단거리와 관련있다. 왤까? BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다. bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다. 그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다. 예시를 보자. 시작점 A에서 F까지의 최단경로를 알아본다고 했을 때 bfs를 진행하면서 F를 처음 방문하..
![]()
https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 알고리즘 좋은 단어의 조건은 1. 같은 단어끼리 짝을 지을 때 2. 선끼리 교차가 불가능하다는 것이다. 그림을 통해 이해하면 쉽다. 만약 문자 A가 나오면 스택 맨위값(top : stack[-1])이 A일 경우, 같은 문자이니까 스택에서 문자 A를 pop한다. B인 경우도 마찬가지로 작업을 진행한다. 이렇게 넣고 빼는 과정을 반복하다보면, 교차 없이 짝이 다 맞는 단어는 스택에 있는 모든 값을 비워주게된다...
