'DFS' 태그의 글 목록

[BOJ / 백준] 2668 숫자고르기 (G5^ / DFS) - Python

링크https://www.acmicpc.net/problem/2668 문제 해석세로로 2칸, 가로로 n개의 칸으로 이루어진 표가 주어짐첫 번째 행에서 뽑은 숫자의 집합과, 첫 번째 행과 같은 열에서 뽑은 두 번째 행의 숫자의 집합이 동일해야 함위를 만족하며 최대로 구할 수 있는 숫자 개수는? 입력첫 번째 줄 : n n : 숫자의 개수 n개의 줄 : 2번째 줄에 들어갈 숫자 출력 뽑힌 정수의 개수를 출력 뽑힌 정수들을 오름차순으로 출력 풀이 & 코드 해석문제의 예제를 그려보면 위와 같습니다. 정답은 1, 3, 5인데 결국 사이클을 가지는 경우, 즉 나 자신으로 돌아올 방법이 있는 경우 정답이 된다는 것을 알 수 있습니다. 사이클의 종류는 크게 1과 3이 이루는 1대1 사이클, 5와 ..

개인 공부/1Day_1Algo 2024. 7. 2. 10:41

[BOJ / 백준] 16562 친구비 (G4 / DFS) - Python

링크https://www.acmicpc.net/problem/16562 문제 해석돈을 주면 친구가 되어 준다. 친구의 친구는 친구다. 가진 돈의 한도 내에서 가장 적은 비용으로 모두와 친구가 될 수 있는 방법을 구하라. 입력 첫 번째 줄 : n m k n : 학생 인원 수 m : 친구 관계 수 k : 가지고 있는 돈두 번째 줄 : n명의 학생이 각각 친구비로 원하는 돈m개의 줄 : f1 f2 f1 : 친구 1 f2 : 친구 2 -> 1, 2는 서로 친구사이 출력 모든 학생을 친구로 만들 수 있으면 최소 비용 출력 친구를 다 사귈 수 없으면 "Oh no" 출력 특이사항 친구 숫자는 1부터 시작함 풀이 & 코드 해석연결요소로 이어진 사람들은 한 명만 매수해도 모두 친구가 됩..

개인 공부/1Day_1Algo 2024. 6. 30. 10:38

[BOJ / 백준] 15971 두 로봇 (G4^ / DFS) - Python

링크https://www.acmicpc.net/problem/15971 문제 해석N개의 방이 존재하고, 통로는 N-1개 존재한다.두 로봇 간에 통신이 필요하고, 통신을 위해서는 로봇 사이에 1개의 통로만 존재해야 한다.통신을 하기 위해 두 로봇이 이동해야 하는 최단 거리는? 입력 첫 번째 줄 : n, a, b n : 방 개수 a : 1번 로봇 위치 b : 2번 로봇 위치 나머지 줄 : s, e, d s : 시작점 e : 끝점 d : 길이 출력 로봇이 서로 통신하기 위해 현재 위치에서 이동해야하는 거리합의 최솟값 풀이 & 코드 해석bfs나 dfs와 같은 그래프 탐색 기법을 사용하면 풀 수 있는 문제입니다. 저는 dfs를 통해 a부터 끝까지 탐사하면서 지나간 통로의 길이를..

개인 공부/1Day_1Algo 2024. 6. 28. 09:52

[BOJ / 백준] 2644 촌수계산 (S2 / DFS) - Python

링크https://www.acmicpc.net/problem/2644 문제 해석촌수계산 부모-자식 관계는 1촌 더 멀어지는 경우 촌수가 늘어남 입력 첫 번째 줄 : n n : 사람 수 두 번째 줄 : a, b 촌수를 구해야 하는 사람 세 번째 줄 : m m : 부모 자식 관계 수 나머지 줄 : m개의 부모 자식 관계 출력 두 사람의 촌수를 출력촌수를 나타낼 수 없으면 -1 풀이 & 코드 해석어제 풀었던 바이러스와 다르게 촌수계산은 a라는 노드와 b라는 노드가 얼마나 떨어져 있는지를 계산해야 합니다. 따라서 그래프를 순회하면서 시작 정점으로부터 얼만큼 떨어져 있는지를 매개변수로 추가하여 문제를 해결하였습니다. 코드def dfs(num, dis): global b, ans ..

개인 공부/1Day_1Algo 2024. 6. 27. 09:39

[BOJ / 백준] 2606 바이러스 (S3 / DFS) - Python

링크https://www.acmicpc.net/problem/2606 문제 해석컴퓨터 바이러스는 동일한 네트워크에 연결된 다른 PC로 감염된다. 1번 컴퓨터가 바이러스에 감염되었을 때 1번 컴퓨터로 인해서 감염된 컴퓨터의 개수를 구하라. 입력 첫 번째 줄 : n n : 컴퓨터의 수 두 번째 줄 : m m : 네트워크 상에 연결된 컴퓨터 쌍의 수 나머지 줄 : m개의 쌍 정보 출력 1번 컴퓨터로 인해 감염된 PC 수 풀이 & 코드 해석그래프에서 연결된 노드의 개수를 찾는 문제입니다. 인접 리스트를 통해서 구현을 시도하였으며, 새롭게 노드를 방문할 때마다 개수를 count하면서 정답을 구하였습니다. 코드def dfs(num): global ans v[num] = True ..

개인 공부/1Day_1Algo 2024. 6. 26. 12:35

[Baekjoon] 백준 1261 알고스팟 (G5^ / 다익스트라) - Python

링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 해석 미로의 크기는 N * M 미로는 빈 방(0) 또는 벽(1)으로 이루어져 있음 벽은 부술 수 있으며, 부수지 않으면 해당 칸으로 이동할 수 없음 이동은 상하좌우로 이동 가능 (1,1)에서 (N, M)으로 이동하기 위해서 최소 몇 개의 벽을 부셔야 하는가? 풀이 & 코드 해석 문제를 해결하기 위해서 먼저 DFS 방식으로 풀어보았습니다. def dfs(x, y): ..

개인 공부/코딩 테스트^ 2024. 3. 22. 18:14

[Baekjoon] 백준 14502 연구소 (G4 / DFS, BFS) - Java

링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해석 - 문제 정의 연구소 크기 N*M 바이러스가 인접한 칸으로 퍼져 나갈 수 있음 벽으로 막히면 바이러스가 퍼지지 않으며, 퍼지지 않은 벽을 3개 세웠을 때 바이러스가 퍼지지 않는 최대 영역 개수 구하기 1 벽 2 바이러스 - 입력 첫 번째 줄 : N M # 세로 가로 나머지 줄 : 지도 - 출력 안전영역의 최대 크기 풀이 & 코드 해석 각각의 알고리즘은 쉽지만 여러 알고리즘을 혼합해서 사용해야하..

개인 공부/코딩 테스트 2023. 4. 15. 10:22

[Baekjoon] 백준 15683 감시 (G4^ / DFS) - Java

링크 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해석 - 문제 분석 CCTV는 총 5가지가 존재함 1번 : 1방향 2번 : 대칭적인 2방향 3번 : 수직인 2방향 4번 : 3방향 5번 : 4방향 CCTV는 90도 각도로 회전이 가능함 CCTV는 벽을 뚫을 수 없음 CCTV가 CCTV를 뚫고 감시는 가능 CCTV로 볼 수 없는 사각지대가 최소가 되도록 CCTV를 회전시키기 - 입력 첫 번째 줄 : N M # N=세로, M=가..

개인 공부/코딩 테스트^ 2023. 4. 14. 11:42

[Baekjoon] 백준 13023 ABCDE (G5^ / DFS, 그래프) - Java

링크 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 해석 A -> B -> C -> D -> E 관계를 가지는 친구가 있는지를 구하시오. 코드 package algo.bj.g5_13023; import java.io.*; import java.util.*; public class Main { static ArrayList[] list; static boolean[] v; static int answer; public static void main(String[] args) throws Exception { BufferedReader br = ..

개인 공부/코딩 테스트^ 2023. 3. 6. 09:49

[Baekjoon] 백준 2023 신기한 소수 (G5^ / DFS, 소수) - Java

링크 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 해석 N자릿수를 가지는 숫자 중 신비한 소수(자릿수가 N, N-1, N-2, N-3... 이 모두 소수가 되는 소수)를 출력하라 코드 package algo.bj.g5_2023; import java.io.*; import java.util.*; public class Main2 { static StringBuilder sb; static int N; public static..

개인 공부/코딩 테스트^ 2023. 3. 5. 23:36

[Baekjoon] 백준 11724 연결 요소의 개수 (S2^ / DFS, 그래프) - Java

링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해석 노드 N개, 간선 M개가 주어질 때 연결 요소 구하기 연결 요소 : 연결된 간선으로 연결된 노드들을 하나의 덩어리로 보았을 때, 전체 그래프의 덩어리 개수 코드 import java.io.*; import java.util.*; public class Main { static ArrayList[] list; static..

개인 공부/코딩 테스트^ 2023. 3. 4. 11:06

[알고리즘] DFS

DFS 개념 DFS : 깊이 우선 탐색 (==장자 우선 탐색) BFS : 너비 우선 탐색 완전 탐색 기법 중 하나 스택(재귀)를 사용함 재귀는 부를 때마다 함수를 시스템 스택에 쌓기 때문에 결국 스택을 사용한 것과 동일한 효과를 가져옴 시작지점에서부터 끝점까지 이동하면서 모든 경우의 수를 탐색 -> 저렴한 비용을 뽑는 문제에서 사용함 앞선 BFS 정리 자료에서 보셨겠지만, DFS는 BFS와 서로 상반되는 개념입니다. DFS는 탐색 시 같은 level에 위치한 노드들을 먼저 탐색하는 BFS와 달리, 한쪽 방향으로 깊이 탐색한 후, 거슬러 올라가면서 나머지를 탐색하는 알고리즘입니다. 그래서 이를 첫번째 자식을 가장 먼저 생각하는 장자 우선 탐색이라고 생각하셔도 좋을 것 같습니다. BFS : 2 -> 7 ->..

개인 공부/알고리즘 2023. 2. 24. 15:07

[SWEA] 1952 수영장 (D0^ / DFS) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&problemTitle=%EC%88%98%EC%98%81%EC%9E%A5&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 - 문제 해석 수영장은 1일권, 1개월권, 3개월권, 1년권이 있음 수영장을 사용할 수..

개인 공부/코딩 테스트^ 2023. 2. 19. 20:05

AngelPlayer`s Diary