DFS6 백준 [자바 java] 16562번 : 친구비 문제설명준석이는 친구를 사귀기 위해서는 친구비를 내야한다.이 때 친구비를 내서 사귄 친구의 친구는 그냥 사귈 수 있다. 모든 친구를 사귀기 위한 친구비의 최소비용은? 풀이dfs로 풀었다. 한 무리를 탐색할 때마다 그 무리 중 친구비가 가장 적은 비용을 구한다.그 친구비의 합이 준석이가 가지고 있는 비용보다 작으면 Oh no를 출력한다.package org.example;import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in.. 2025. 3. 4. 백준 [자바 java] 9466번 : 텀 프로젝트 문제설명n명의 사람들이 있고, 이 사람들이 원하는 팀원이 주어진다고 할 때, 그 어떤 팀에도 속하지 못하는 사람이 있을 수 있다. 이 사람들의 명수를 구하여라 풀이처음에는 혼자 팀을 하고싶어하는 사람과 팀을 하고싶어하는 사람들을 팀에 속하지 못하는 사람으로 분류하고, 또 그 사람과 팀을 원하는 사람을 제외하고.... 이런식으로 문제를 풀었는데 광탈을 해버렸다. 그래서 여러 반례를 찾아보니, 스스로와 팀을 원하는(혼자 팀을 원하는) 사람들이 없는데도, 팀을 이루지 못하는 경우도 있었다.사이클에 포함되지 못하는 경우! 그래서 이 경우를 제외해야한다. 역시,, 가능한 사람들을 보고 빼는게 맞는거같다. 이렇게 하니까 너무 많은 반례를 지나친다 그래서 while문을 통해 계속해서 탐색하다가 이미 방문한 노드를 마.. 2025. 3. 1. 백준 [자바 java] 2573 : 빙산 정말정말정말 오랜만에 알고리즘 문제를 풀었다. 감이 많이 줄어든 것 같다. 앞으로 좀 가끔이라도 풀어야겠다. 문제https://www.acmicpc.net/problem/2573 해설이 문제는 크게 두가지 문제가 있다.1년뒤 빙하의 배열을 만들기빙하의 덩어리 수를 체크하기빙하 덩어리 확인하기 static class xy{ int x; int y; xy(int x,int y){ this.x = x; this.y = y; } }우선 x,y 좌표를 스택에 저장하기 위해서 클래스를 하나 만들었다. int[] dx = {0,1,0,-1}; int[] dy = {1,0,-1,0};또한 dx, dy 테크닉을 사용하기 위해서 위와 같은 배열을 만들었다. Stack .. 2024. 11. 15. 코드트리 [자바 java] 두 방향 탈출 가능 여부 판별하기 https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai dfs를 이용해서 탈출 가능 여부를 판단하는 문제이다. 0,0에서 출발해서 오른쪽, 아래로 갈 수 있는 길이 있는지 하나씩 탐색한다. 만약 갈 수 있다면, stack에 넣고 다시 그 위치에 대한 오른쪽, 아래를 탐색한다. 위와 오른쪽의 격자를 탐색하기 위해 dx,dy테크닉을 사용했고, 위, 왼쪽으로.. 2023. 7. 31. 코드트리 [자바 java] 그래프 탐색 https://www.codetree.ai/missions/2/problems/graph-traversal/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 정점과 간선이 주어지고, 1에서 출발해서 도착할 수 있는 정점을 구하는 문제이다. 처음에는 유니온파인드로 풀어야하나 했지만, 생각해보니 dfs로 탐색하고, 방문한 수로 같은 그래프에 해당하는 정점의 갯수를 구하는게 더 빨랐다. 리스트를 이용해서 각 정점과 연결되어있는 정점들을 저장했고, 1번리스트에 있는 정점들부터 stack에 차례로 쌓으면서 dfs를 수행했다. import j.. 2023. 7. 27. 백준 [java 자바] 2251번 : 물통 문제를 보고 처음 계획을 세울 때 감이 잘 잡히지 않았던 문제이다. import java.util.*; import java.io.*; class three { int a; int b; int c; three(int a, int b, int c){ this.a = a; this.b = b; this.c = c; } } class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); StringBuilder sb.. 2022. 8. 19. 이전 1 다음
