반응형 Computer Science/Algorithms10 그래프의 탐색, bfs 와 dfs 1. 개요 그래프의 모든 정점을 방문하기 위한 방법으로 깊이우선탐색(depth first search)과 너비우선탐색(breadth first search) 가 있습니다. 깊이우선탐색은 하나의 정점에서 인접한 다음 정점을 방문한 뒤, 다시 새로 방문한 정점과 인접한 정점을 방문하는 방식으로, 한 우물만 죽어라 파는 방법입니다. 반면 너비우선탐색은 시작정점과 인접한 정점 모두를 방문한 뒤, 방문한 정점들 중에서 한 놈을 골라 그와 관련된 정점들을 모두 터는 방식입니다. 마치 저 반역자의 삼족을 멸하라! 하는 것처럼.. 2. 알고리즘 (1) dfs a. 정점 하나를 방문합니다. b. 방문한 정점과 인접한 정점 중 방문하지 않은 정점 하나를 방문합니다. c. 해당 정점을 중심으로 다시 깊이 우선 탐색을 시작합.. 2021. 11. 1. 집합 - Set 구현하기 문제 : https://www.acmicpc.net/problem/11723 1. 개요 Set 라이브러리에 있는 삽입 삭제 등의 기능을 구현하는 문제입니다. 왠지 Set 를 사용하면 반칙인 것 같지만 굳이 다른 자료형을 이용하라고 낸 문제는 아닌 것 같아서 그냥 Set를 썼습니다. 2. 고난과 역경 구현 자체는 어렵지 않으나 관건은 시간 제한입니다. 보통 출력하면 생각나는 System.out.print 가 문제였습니다. 출력값을 어디에 저장해뒀다가 한꺼번에 출력을 할 필요가 있어 보였고 BufferedWriter로 바꿨더니 통과할 수 있었습니다. 3. 대안 문제상에서 입력 원소 값의 범위가 정해져 있기 때문에 2진수의 비트연산을 이용해서 조금 더 간단하게 해결할 수 있습니다. 10 9 8 7 6 5 4 .. 2021. 11. 1. 로봇 청소기 문제 : https://www.acmicpc.net/problem/14503 1. 개요 n x m 바닥에서 순회를 하는 문제입니다. 2. 고난과 역경 모든 문제 해결은 문제를 꼼꼼히 읽는 것에서 시작합니다. 문제를 잘못 이해한 죄로 한참을 헤맨 끝에 후진을 과소평가했다는 것을 깨닫게 되었습니다. 문제의 조건에 따르면 이 청소기는 '청소를 한 곳' 과 '벽' 을 구분할 수 있고, 사방에 청소할 곳이 없더라도 뒤가 벽으로 막힌 것이 아니라면 계속 후진하여 탈출이 가능합니다. 3. 코드 import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.next.. 2021. 10. 31. 방 번호 문제 import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int n = 0; int[] numSet = new int[11]; Arrays.fill(numSet, 1); /* 목표 숫자의 범위를 지정 */ if(num == 1000000) n = 1000000; else if(num >= 100000) n = 100000; else if(num >= 10000) n = 10000; else if(num >= 1000) n = 1000; else if(num >= 100) n = 100; else if(num >= 10) n.. 2021. 10. 30. 이전 1 2 다음 반응형
