Dazzling 개발 노트

[백준] 4963 - 섬의 개수 (Java) 문제 https://www.acmicpc.net/problem/4963 풀이/후기 일반적인 그래프탐색 문제지만, 대각선으로 인접한 경우에도 한 가지로 판단하는 문제였다. 즉, 상하좌우 + 대각선까지 고려해야한다. 대각선은 현재 지점을 기준으로 {-1,-1}, {-1,1}, {1,1}, {1,-1}인 것만 생각한다면 쉽게 풀 수 있다. dir에 상하좌우 4개와 대각선 4개까지 총 8개 경우를 넣어주면 된다. 예전엔 대각선 어려울 줄 알고 겁먹었었는데, 생각해보니 굉장히 간단하게 풀 수 있었다~ 코드 package GraphTheory; import java.io.*; import java.util.*; public class Problem4963 { static..

[백준] 16956 - 늑대와 양 (Java) 문제 https://www.acmicpc.net/problem/16956 풀이/후기 스페셜 저지 문제로, 예제에 나온 출력과 내 결과가 달라도 문제의 조건이 맞다면 정답처리가 된다. 처음 예제 출력을 보고 울타리를 어떻게 효율적으로 배치하는 코드를 짜야하는지 막막했다. 그러나 울타리 개수가 한정된 것이 아니고, 효율적으로 배치하라는 조건도 없기 때문에 그저 양과 늑대가 만나지만 않는다면 울타리는 자유롭게 설치가 가능하다. 예제 3 출력을 보면 울타리가 하나 들어가 있는데, 어차피 늑대가 존재하지 않기 때문에 울타리가 없어도 정답이다. 그래서 BFS를 이용해 늑대 주변에 모두 울타리를 설치하는 방식으로 풀었다. 단, 늑대와 양이 1칸 이내에 존재한다면 무조건 ..

[백준] 14889 - 스타트와 링크 (Java) 문제 https://www.acmicpc.net/problem/14889 풀이/후기 백트래킹 유형은 그동안 외면하다가 처음 풀어본 것 같다. 처음에는 그래프탐색이나 DP를 활용한 풀이를 생각했었다. 결국 DFS를 활용한 백트래킹으로 풀었다. N명을 2개의 팀으로 나누기 위해 depth 변수를 활용한다. depth+1을 계속해서 호출하며 N명의 절반이 될 때까지 재귀를 호출한다. 즉, 이렇게해서 팀을 나눈 것이다. 팀은 두개의 팀이기 때문에 true, false로 구분이 가능하다. 나는 true팀, false팀이라고 이해하니 편했다. 그리고 팀이 결성된 후에 각 팀의 점수를 비교하여 최소값을 구해주면 된다. 처음 생각할 때는 어려운데, 소스코드를 보면 또 ..