윤프로 | 코드가 개발새발해

[문제출처 | https://www.acmicpc.net/problem/1012 ] 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 기본적인 BFS 코드를 가지고 무난하게 적용해 볼 수 있는 문제였다. 단, 주의할 점은 가로길이, 세로길이, 가로좌표, 세로좌표의 순서로 받는다는 점! 보통 행->열 순으로 받는데 이 경우는 열->행 순으로 입력이 들어온다. 비슷한 문제로 백준 섬의 개수 문제가 있다. 이웃한(4방) 1의 뭉텅이가 몇개인지 찾는 문제였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util..

[문제출처 | https://www.acmicpc.net/problem/11558 ] 구현 그래프 이론 그래프 탐색 시뮬레이션 처음에 문제를 접하고 아 쉽네~ 했다가 이상한 곳에서 파고들다가 길을 잃었다.. 처음엔 1차원 배열에 인덱스는 각 사람의 번호라치고, 값은 그 사람이 가리키는 사람의 번호를 담았다. 그리고 while문을 돌며 주경이 번호(N)가 걸릴 때까지 돌면서 주경이를 가리키는 사람의 인덱스를 출력하게 접근했는데.. 그래프 탐색인데 인접행렬이나 인접리스트를 쓰는게 낫나? 사이클이 돌면?, 주경이를 가리키는 애가 없거나, 주경이를 가리키는 애가 희현이로부터 연결되어 있지 않다면? 위의 생각들로 class Node를 만들었다가 배열리스트를 썼다가, 연결리스트를 썼다가... 삽질이란 삽질은 다 했..

[문제출처 | https://www.acmicpc.net/problem/16173 ] 구현 그래프 이론 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 깊이 우선 탐색 기본적인 BFS 로직으로 풀 수 있는 문제였다. 보통 4방 탐색인 것과 달리 오른쪽, 아래 2방 탐색이라는 점. 그리고 map에 쓰여진 칸만큼 이동한다는 것 정도만 주의하면 될 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 통과 124ms public ..

[문제출처 | https://www.acmicpc.net/problem/11729 ] 재귀 학부 시절 과제로 받았던 하노이 탑... 이론은 알겠는데 이걸 코드로 짜라구요..? 눈물을 머금었더랬지 재귀의 시작, 재귀의 꽃이라 할 수 있겠다. 이론은 간단하다. 문제 설명 그대로 1번 장대에서 3번 장대로 원판을 모두 옮기는 것! 단, 크기가 제일 큰 게 맨 아래로 작은 게 맨 위에 위치하도록 한다. 옮길 땐 한 개의 원판씩, 작은 원판 위에 큰 원판이 올라갈 수 없다. 먼저 장대를 시작, temp, 최종 으로 생각하고 풀어나가도록 한다. 이동하는 횟수가 최소가 되어야 한다는 점에서 여러가지 수를 가정해야 하나? 했는데 그냥 불필요한 이동을 하지 않으면 된다.. 이동 횟수를 먼저 출력하고 그 다음에 이동한 이..

[문제출처 | https://www.acmicpc.net/problem/2920 ] 구현 역시 첫 주의 시작은 무난하게 시작하는 게 좋을 것 같아서 고른 브론즈 구현문제. 첫 문장을 읽기 시작했을 때, "오. 문자열로 들어오나?" 했는데 예제를 보니 그냥 숫자로 들어온다! 이건 뭐 soooooo eassssssy 한데~ 하고 짜고 보니, 뭔가..이것보다 더 간단하고 효율적으로 짤 수 있을 것 같은데 싶다.. 방법1. 그냥 Arrays 클래스의 equals 메소드를 이용해 배열의 내용을 비교하여 출력 import java.io.*; import java.util.*; // 통과 124ms public class Main { static int[] asc = { 1, 2, 3, 4, 5, 6, 7, 8 };..

[문제출처 | https://www.acmicpc.net/problem/2606 ] 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 1번 컴퓨터(정점)로부터의 인접 정점 개수를 구하는 문제라고 생각했다. 그래서 DFS를 이용해 매개변수로 1을 넘기고 그것과 연결된 노드를 찾아가며 카운트하도록 했다. 보통 for문이라고 하면 int i = 0 이 익숙하지만 int가 자료형이고 Node도 자료형으로써, 배열로 만든 Node를 반복문으로 돌리는 것도 가능하다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; // 통과 132..

[문제출처 | https://www.acmicpc.net/problem/1325 ] 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 정답비율 안 보고 이번 주 스터디에 제시한 문제... 그래프 탐색 분류에서 실버길래 괜찮지 않을까~ 가져왔는데 일단 테케도 하나뿐이고 보아하니 시간초과나 메모리초과로 꽤나 골치아픈 문제였다.(오답)첫 풀이는 백준 바이러스 문제와 비슷해보여서 단방향 연결로 받는데 이때, 'A가 B를 신뢰할 때 B를 해킹하면 A를 해킹할 수 있다는' 부분에서 B->A 로 접근을 했다. 1. 근접리스트로 B행에 A리스트를 쌓고 ( adjList[b].add(a) ) 2. 배열을 돌며 각 행 리스트의 사이즈 값이 큰 인덱스를 찾아(=신뢰되는 경우가 많은 컴퓨터) 3. 배열을 돌며 그 인덱..