생각하는 아져씨

24444번: 알고리즘 수업 - 너비 우선 탐색 1https://www.acmicpc.net/problem/24444 문제 정의입력으로 주어지는 간선 정보로 BFS를 수행하고 각 노드의 방문 순서를 출력한다. 접근 방법BFS 탐색 문제 해설각 노드 정보를 이차원 리스트 정보로 받는다.무방향 그래프 이므로 양방향 간선으로 간주하고 양쪽의 정보를 다 입력한다.시작 노드인 R 부터 DFS를 수행한다. 풀이import sys from collections import deque input = sys.stdin.readline N, M, R = map(int, input().split()) graph = [[] for _ in range(N+1)] visited = [False] * (N+1) order = [0..

24479번: 알고리즘 수업 - 깊이 우선 탐색 1https://www.acmicpc.net/problem/24479문제 정의입력으로 주어지는 간선 정보로 DFS를 수행하고 각 노드의 방문 순서를 출력한다. 접근 방법DFS 알고리즘 활용 문제 해설각 노드 정보를 이차원 리스트 정보로 받는다.무방향 그래프 이므로 양방향 간선으로 간주하고 양쪽의 정보를 다 입력한다.시작 노드인 R 부터 DFS를 수행한다. 풀이import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N, M, R = map(int, input().split()) # 정점 개수, 간선 수, 시작 정점 graph = [[] for _ in range(N+1)] # 연결 그래프 vis..

플로이드 와샬(Floyd-Warshall)동작 과정A → 1번 노드 → B 로 가는 최단 거리 비용은?점화식시간복잡도코드참조 플로이드 와샬(Floyd-Warshall)모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘이다. 👉 최단경로를 구하는 다익스트라와 다른점은?다익스트라는 ‘한 지점에서 다른 특정 지점까지의 최단 경로’를 구하는 알고리즘인 반면, 플로이드 와샬은 모든 노드에 대한 최단 경로를 찾는 것이 목적이다.또한 다익스트라는 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾아야 하는데, 플로이드 와샬은 찾지 않아도 된다.마지막으로, 다익스트라는 최단거리를 1차원 리스트에 저장하는데, 플로이드 와샬은 2차원 리스트에 저장한다는 특징이 있다. ..

문제 정의접근 방법문제 해설풀이정리참조 https://school.programmers.co.kr/learn/courses/30/lessons/49191 문제 정의선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 returnresults 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미이다. 접근 방법순위가 정해지는 의미가 어떤 것인지 잘 파악해야 한다. 👉 순위가 정해진다 == 나 제외 모든 선수와 경기를 해서 승패가 갈렸다. 또한 i가 k를 이기고, k가 j를 이기면 i가 j를 이긴다는 연쇄적인 특징을 반영해 그래프를 업데이트 해야한다.플로이드 와샬 알고리즘을 활용해 풀 수 있다. 문제 해설[딕셔너리 사용할 경우..

https://school.programmers.co.kr/learn/courses/30/lessons/49189문제 정의n개의 노드가 있고 간선에 대한 정보가 주어진다.간선은 양방향이며, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 한다.가장 멀리 떨어진 노드란? → 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다. 접근 방법가장 멀리 떨어진 노드의 개수를 구하는데 최단 경로로 이동했을 때 가장 멀리 떨어진 노드이다.따라서 가장 멀리 떨어진 노드까지 최단경로로 이동 했을 때 얼만큼 떨어져있는지?를 알아야 한다. 예를 들면 소요된 거리 또는 비용이라던가? 여기서는 간선에 대한 비용이 주어져있지 않으므로, 간선의 비용을 1로 설정해서 소요 비용을 구할 수 있다.문제에서 최단경로..

14502번: 연구소https://www.acmicpc.net/problem/14502 문제 정의연구실의 바이러스 확산을 막기 위해 연구소에 벽을 세워야 한다. 연구소는 N*M 인 직사각형이고 1*1의 정사각형으로 나뉘어있다고 가정한다.연구소는 빈 칸, 벽으로 이루어져 있는데 일부 칸은 바이러스가 존재한다.0이라면 빈 칸, 1이라면 벽, 2는 바이러스가 존재함을 나타낸다.이 때 안전한 영역 크기의 최댓값을 구해야 한다. 벽은 꼭 3개만 사용할 수 있다. 접근 방법안전 영역은 벽이 세워져서 빈 칸으로 남을 수 있는 ‘0’의 개수를 세면 된다.가장 최댓값의 0의 개수를 찾아서 결과를 출력하면 된다. 일단, 벽 3개가 세워질 위치 3곳을 정해야 하는데 이것은 ‘완전탐색’으로 접근했다. 어차피 N과 M의 크기가..