[유형]bfs [문제링크]https://www.acmicpc.net/problem/13549 [요약]수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. [문제풀이]import syssys.setrecursionlimit(10**7)from collections import deque..

[유형]bfs [문제링크]https://www.acmicpc.net/problem/1697 [요약]수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. [문제풀이]import sysfrom collections import dequedef input(): return sys.s..

[유형]dfs [문제링크]https://www.acmicpc.net/problem/2667 [요약]철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. [문제풀이]import sys# sys.setrecursionlimit(10**7)def input(): return sys.stdin.readline().rstrip()def dfs(x, y): global count if x = n or y = n: return if graph..

[유형]DFS [문제링크]https://www.acmicpc.net/problem/11724 [요약]방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. [문제풀이]백준 온라인 저지의 기본 recursionlimit은 1000이다.sys.setrecursionlimit()을 지정해주지 않으면 재귀 호출 시 런타임 에러가 발생한다.visited[i]==0인 노드가 없어질 때까지 DFS를 수행하면서 answer+=1import syssys.setrecursionlimit(10**7)def input(): return sys.stdin.readline().rstrip()def dfs(graph,visited,v): visited[..

[유형]DFS [문제링크]https://www.acmicpc.net/problem/2606 [요약]어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. [문제풀이]import syssys.setrecursionlimit(10**7)def input(): return sys.stdin.readline().rstrip()def dfs(v,graph,visited): global answer visited[v] = 1 for i in graph[v]: if visited[i] == 0: answer+=1..

[유형]그리디 [문제링크]https://www.acmicpc.net/problem/2437 [요약]첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다. [문제풀이]연속성이 깨지는 부분을 찾으면 된다.weights를 오름차순으로 정렬한다.answer에 추의 무게를 하나씩 더한다. answer+1이 w보다 작다면 연속성이 깨진다는 의미이다.import sysimport heapqdef input(): return sys.stdin.readline().rstrip()N = int(input())weights = list(map(int, input().split()))weights.sort()answer = 0for w in weights: if answer+1