차곡차곡

https://www.acmicpc.net/problem/15591 문제 설명그래프와 유니온-파인드를 활용해 특정 조건을 만족하는 노드(동영상)들의 수를 구하는 문제이다. 그래프 구성동영상들은 노드, 동영상 쌍 간의 USADO 값은 간선의 가중치로 주어진다.총 N개의 노드와 N-1개의 간선이 있으며, 모든 노드는 하나의 연결 그래프를 이룬다. USADO 경로 계산: 두 노드 간의 USADO는 그들을 연결하는 경로의 간선 중 최솟값 아이디어처음 풀이로 BFS를 사용해 탐색했다. 하지만 시간초과가 발생했다. 따라서 union-find 를 사용해 해결했다. 또한 간선을 내림차순 정렬하여 K 이상의 간선만 처리하도록하여 효율성을 높였다. 코드노드 u가 속한 집합의 루트노드를 찾는 find 함수이다. 재귀함수를 ..

https://www.acmicpc.net/problem/14502 아이디어연구소의 최대 크기가 크지 않기 때문에 벽을 세우는 모든 경우의 수를 파이썬의 combination(조합)을 이용해 탐색하면된다.입력받은 연구소에서 빈칸의 좌표와 바이러스의 좌표를 각각 저장한다.빈칸의 좌표 중에서 Combinations를 사용하여 3개를 조합해 탐색한다.해당 조합의 좌표에 벽을 세우고 바이러스를 최대로 확장한다.연구소의 남은 안전구역을 계산한다.남은 안전구역이 최대가 되는 값을 출력한다. 바이러스 확산이때 연구소의 바이러스를 확장할 때에는 BFS를 사용하여 확장하였다.def bfs(temp_graph): q = deque(virus_positions) while q: x, y = q.po..

https://www.acmicpc.net/problem/1743 문제를 보고 바로 BFS를 이용해 상하좌우에 이어진 쓰래기를 탐색해 최대(Max)를 구하면되겠다고 생각했다. 처음 코드 (메모리 초과)from collections import dequeimport sysinput = sys.stdin.readlinedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]result = 0n, m, k = map(int, input().split())trash = [[False]*m for _ in range(n)]for _ in range(k): x, y =map(int, input().split()) trash[x-1][y-1] = Truedef bfs(x, y): cnt = ..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 [출발지,도착지] 형태로 적힌 항공권 정보 List가 주어진다. 출발지는 항상 ICN 공항에서 출발하며 모든 항공권을 사용해야 한다. 이를 만족하는 경로를 Return하고 만약 만족하는 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 Return한다. 접근법 스택에 ICN을 넣어준다. 출발지와 도착지 정보가 담긴 dictionary 배열의 key(출발지) 와 valu..

너비 우선 탐색 (BFS, Breadth First Search) 한 노드에서 시작한 후 시작 노드의 인접한 노드부터 탐색하는 방법이다. 가까운 노드부터 탐색하는 알고리즘 이다. 시작 노드로부터 가까운 정점을 먼저 방문하고 멀리 있는 노드는 마지막에 방문하는 방식이다. 넓게 탐색하는 방식이다. 일반적으로 선입선출 방식인 큐 자료구조를 활용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색이 이루어진다. 특징 여러 갈래중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우에는 DFS는 무한루프에 빠져 종료되지 못하지만, BFS는 동시에 탐색이 진행되기때문에 탐색이 완료될 수 있다. 모든길을 한번씩 탐색하기 때문에..

https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 n개의 노드가 주어지고 1번 노드로 부터 가장 먼 노드의 갯수를 구해서 Return 해주어야 한다. 이때 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 갯수가 가장 많은 노드를 의미한다. 접근법 그래프 이론 알고리즘의 인접 리스트 방식으로 주어진 입력을 변환해준다. 거리(간선 개수)를 저장 해줄 리스트를 만들고 BFS를 사용해 최단 경로의 간선 개수를 센후 저..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 정답 code # 치즈 import sys input = sys.stdin.readline from collections import deque dx = [-1,1,0,0] dy = [0,0,-1,1] # bfs로 외부 공기를 탐색하며 외부공기와 접촉시마다 +1 카운트해줌 def bfs(): queue = deque() #맨 가장자리에는 치즈가 안놓이는 외부공기 queue.append..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 정답 code #벽부스고 이동하기 from collections import deque dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(x,y,z): queue = deque() queue.append((x,y,z)) while queue: a,b,c = queue.popleft() #끝에 도달한경우 결과값 반환 if a == n-1 and b ==..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 정답 code #트리의 지름 from collections import deque import sys input = sys.stdin.readline def bfs(s): queue = deque() visit = [-1] * (v+1) queue.append(s) visit[s] = 0 node_distance = [0,0] while queue: q = queue.popleft..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 정답 code #뱀과 사다리 게임 from collections import deque import sys input = sys.stdin.readline def bfs(v): queue = deque() queue.append(v) visit[v] = 1 while queue: target = queue.popleft() for i in range(..