Completion over Perfection

백준 10026 - 적록색약 (JAVA 자바) 비교적 쉬운편에 속하는 DFS 문제입니다. 쉬운만큼 기초다지기에 좋은 문제입니다. 저는 아래와 같이 풀었습니다. 참고해주세요~ 1. 데이터입력받을 때 1줄씩 받고, charAt 을 통해 한글자씩 잘라서 map[][] 배열에 저장해준다. 2. 색약이 아닌 사람의 경우와 색약인 사람의 경우를 나눠서 2번 DFS를 돌려준다. 3. 색약인 사람의 경우에는 녹색과 적색을 구분 못하므로, G를 R로 모두 바꿔준 후에 DFS를 돌렸다. 4. visits[][] 배열은 두번째 돌리기 전에 초기화를 시켜줘야 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..

백준 2468 - 안전 영역 (JAVA 자바) 기본적인 풀이방법은 유기농 배추(1012번: 유기농 배추 (acmicpc.net))와 크게 다르지 않지만, 차이점은 아래와 같습니다. 1) 물의 높이에 따라서 활성화되는 지역과 안되는 지역을 구분해주고 2) 그에 따라서 DFS 돌린 횟수를 모든 케이스에서 구한 뒤, 3) 그 중에서 가장 최댓값을 구한다. 제가 풀이한 방법을 설명 드리겠습니다. - map[][] 배열을 통해서 주어진 안전 지대에 대한 값들을 받습니다. - visits[][] 배열로 dfs를 돌 때, 특정 지역을 방문했는지 안했는지에 대한 체크를 해줍니다. - copy_map[][]은 강수량에 따라서 잠기는 지역을 체크하기 위한 배열 정보입니다. map[][]을 바로 업데이트하면 안되는 이유가,..

백준 2252 - 줄 세우기 (JAVA 자바) www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 문제집과 굉장히 유사한 문제입니다. 문제집도 같이 풀어보시면 좋을 것 같습니다. PriorityQueue를 이용해서 풀면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 ..

백준 2075 - N번째 큰 수 (JAVA 자바) www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 우선순위큐의 개념을 이해하는 데 좋은 문제 같습니다. 우선순위큐에 다 넣어주고, 5번째 큰 수를 q.poll()로 꺼내주어 출력하면 됩니다. 우선순위큐는 우선순위가 높은(숫자가 작은) 것부터 출력하는 것이 디폴트이기 때문에, 큰수부터 출력하도록 Collections.reverseOrder()를 넣어서 선언해줍시다~ 1 2 3 4 5 6 7 8 9 10 11 12 13 ..

백준 4963 - 섬의 개수 (JAVA 자바) www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net DFS인데 다른 문제들과는 다르게 8방향을 모두 봐야합니다. (상하좌우 + 각 대각선) 그 부분만 주의해서 코딩하시면 됩니다. 어려운 문제는 아니었습니다. 아! 그리고 while문을 사용해서 0 0 이 들어올때까지 돌려줘야됩니다. (입력의 마지막줄에 0이 두개 들어옴) 자세한 내용은 코드를 참고해주세요~ 1 2 3 4 5 6 7 8 9 10 11 12 13 1..

백준 11724 - 연결 요소의 개수 (JAVA 자바) 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 기본적인 DFS 문제입니다. 아래 주의사항들을 참고하셔서 코드 짜시면 됩니다. 1. 중간에 간선이 끊겨있을 수 있으므로, 방문하지 않은 지점에서 DFS가 다시 시작할 수 있도록 해줍니다. (for문 안에 dfs를 배치할 것) 2. DFS가 한번 끝날때마다 cnt 변수를 +1 해준 뒤, 마지막에 ..

백준 2606 - 바이러스 (JAVA 자바) www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net DFS의 가장 기본이 되는 문제 같습니다. 풀이방법은 아래의 사항들을 참고하여 풀어주시면 됩니다. 1. 시작지점은 무조건 1번 컴퓨터에서부터 시작되므로, 1번에서 연결된 컴퓨터들만 모두 돌면서 wasted 변수를 증가시켜준다. 2. 한번 방문한 지점은 방문체크를 해주고, 다시 방문 안하도록 해준다. 3. 간선으로 연결되어 있는 곳은 DFS를 돌려주고, DFS를 돌기 전에 ..

백준 2667 - 단지번호붙이기 (JAVA 자바) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 단순한 DFS 문제인줄 알았는데, 너무 어려웠어요. 예제코드는 잘 돌아가서 돌려봤는데 계속 실패가 떠서 댓글에 있는 반례를 가지고 코드 수정을 했습니다. 아래 사항에 주의하여 진행하셔야 합니다. 1. 지도는 숫자가 아닌 문자열로 들어옵니다. 문자열로 받아서 charAt 으로 잘라서 저장해야됩니다. (귀찮...) 2. 오름차순으로 출력을 해야합니다. Arrays.sort를 활용해서 오름차순으로 정리 후 출력하도록 합시..