[백준,BOJ 2580] 스도쿠 (JAVA 구현,추가풀이)

-내 생각 여태 푼 백 트래킹 알고리즘을 이용하는 문제들 중 N-QUEEN문제만큼 고민 한 문제이다. 그래도 N-Queen문제를 한 번 풀어봤던 탓인지, 어떻게 풀어야 할지 감을 잡는데 오랜 시간이 걸리지는 않았다. 이 문제까지 풀어보고 느낀 건 백 트래킹 알고리즘의 경우 별도의 체크 메서드가 반드시 필요하다는 점이다. 글에서만 봤지만 무슨 소리인지 몰랐던 '유망한 노드'를 식별하는데 필요하다고 생각한다. 즉, 조건에 해당하는 사항만 DFS로 재귀호출을 해주면 된다. 우선 스도쿠 문제의 경우 대다수의 사람들이 조건을 알 거라고 생각한다. 물론 문제에도 쓰여있다. 즉 가로, 세로, 3X3크기의 박스에 1부터 9까지의 숫자가 겹치지 않고 들어가야 한다. 여기까지만 읽으면 백 트래킹을 위한 조건을 어떻게 세워..

→2020.11.19

코테/백준 온라인 저지(BOJ)

[백준,BOJ 9663] N-Queen (JAVA 구현,추가풀이)

글을 쓰기에 앞서 블로그 개설 후 방문자 수가 늘었다. ㅎㅎㅎ 그냥 개인 기록용 블로그로 쓰고 있는 거여서 방문자 수는 별로 신경 안 쓰고 있는데, 사람들이 찾아와 준다는 게 신기했다. 물론 글이 유익했는지는 모르겠지만.. 그래도 그중에는 도움을 받아가는 분이 있다고 믿고 싶다. ㅎㅎ 문제를 보자! -내 생각 백 트래킹 알고리즘 중 가장 유명한 문제라는데 확실히 검색해보면 다른 많은 분들이 관련해서 글들을 많이 올리신 것 같다. 하지만 문제 자체는 쉽지 않다고 생각한다.. 실제로 이 문제를 풀기 위해서 3일을 소요했으니..(여러 개인 사정으로 자세히 고민해보지는 못했지만 ㅎㅎ) 우선 문제 자체는 어렵지 않다. 체스의 퀸을 활용한 문제인데, 체스의 룰에 대해서는 이전부터 알고 있었기 때문에 퀸이 상하 대각..

→2020.11.17

코테/백준 온라인 저지(BOJ)

[백준,BOJ 15652] N과 M(4) (JAVA 구현,추가풀이)

-내 생각 백준 온라인 저지에서 단계별 풀어보기 탭의 백트래킹 카테고리에 있는 마지막 N과 M문제이다. 이번 문제가 가지는 앞선 문제들과의 차이점은 우선 중복을 허용하며, 각 자리의 숫자들은 자신보다 앞에 있는(먼저 오는) 숫자보다 크거나 같아야 한다는 조건이 있다. 그렇기 때문에 처음 봤을 때 N과 M(3) 문제에서 조건만 추가해주면 될 것 같다고 생각했으며, 시간제한이 1초이기 때문에 마찬가지로 BufferedWriter클래스와 BufferedReader클래스를 사용해주었다. -해법 추가된 한 줄의 조건문은 코드를 보면서 이해해 보자. import java.io.*; import java.util.*; public class Main { static int m,n; static int list[]; ..

→2020.11.17

코테/백준 온라인 저지(BOJ)

[백준,BOJ 15649] N과 M(2) (JAVA 구현,추가풀이)

-내 생각 백준 15649번 문제인 N과 M(1)이 순열을 출력하는 문제였다면, 이번 문제는 조합을 출력하는 문제였다. 어떤 블로그에서 봤던 글에 의하면 순열과 조합 문제는 DFS를 이용해 구현하면서, 순열의 경우에는 순열의 끝을 기준으로 재귀 호출을 종료하며, 조합의 경우에도 재귀 호출을 종료하는 조건은 같지만, 중간 처리 부분에서 하나의 인자가 더 필요하다는 것을 알 수 있었다. 하지만 글을 자세히 보지 않아 어떤 인자가 들어가야 할지 고민해보다 순열은 매 순간마다 1부터 끝 숫자까지 탐색해야 하고 조합은 (1,2)나 (2,1)을 같은 경우로 보기 때문에 매 순간마다 1부터 볼 필요가 없다는 사실을 떠올리고 반복문의 시작 부분을 변경해주면 될 것 같다는 큰 틀을 잡고 구현해보았다. -해법 이전에 N과..

→2020.11.17

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1697] 숨바꼭질(JAVA 구현, 추가풀이)

-내 생각 일단 이 문제를 풀었을 때 굉장히 뿌듯했다. 왜냐하면 알고리즘 공부를 막 시작했을 때 이와 비슷한 문제를 만나서 어떻게 해결해야 할지 감도 안 잡히고 노트만 더러워졌었는데, 이번엔 풀어냈다. 그렇다고 이 문제를 처음 봤을 때 딱 해결법이 떠오른 것은 아니었다. 우선 고민을 해보았다. 예제 입력에서 수빈이의 첫 위치가 5이기 때문에 5에서 1일이 지날 때 갈 수 있는 곳은 4, 6, 10이다. 이와 같이 그래프를 그려서 생각해보니 어느 정도 윤곽이 잡혔고, 이전에 풀었던 토마토 문제나 최단경로 찾는 문제처럼 방문 여부배열에 1씩 증가시키면 될 것 같다는 생각까지는 했는데 조건문 부분에서 고민을 많이 했다. 왜냐하면 문제에서 동생을 찾을 수 있는 가장 빠른 시간을 묻기 때문에 최솟값을 찾아야 한다..

→2020.11.13

코테/백준 온라인 저지(BOJ)

[백준,BOJ 7569] 토마토2(JAVA 구현,추가풀이)

-내 생각 이 문제는 백준 7576 토마토 문제와 유사한 문제로 이번 문제에서는 단순히 토마토 상자가 하나가 있는 것이 아니라 토마토 상자가 여러 개 있을 경우에 대해서 물어보는 다차원 배열을 응용한 문제였다. 알고리즘 공부를 시작하고 다차원 배열을 사용하는 문제는 처음인 거 같은데 그래서 그런지 기존에 알고 있던 면, 행, 열 개념이 명확하지 않아서 조금 찾아본 후 구현했다. 자바에서 3차원 배열의 경우 int arr [][][] = new int [면], [행], [열]로 객체를 만들면 되며, 각 부분의 길이도 헷갈렸는데 출력으로 확인해본 바로 arr.length는 면의 길이(즉, 면의 개수) arr [면]. length가 행의 길이, arr [면][행]. length가 열의 길이가 된다. 뿐만 아니..

→2020.11.13

코테/백준 온라인 저지(BOJ)

[백준,BOJ 7576] 토마토(JAVA 구현, 추가풀이)

-내 생각 알고리즘 문제를 계속해서 풀다 보니까 이제 언제 DFS를 쓰고 언제 BFS를 써야 하는지 감이 좀 잡히는 듯하다. 이번 문제의 경우에는 토마토가 인접한 토마토를 1일이 지날 때마다 익게 한다는 것이 포인트라고 생각했다. 즉 초기에 주어지는 익은 토마토를 기준으로 인접한 토마토를 모두 익게 만들면 되는 것인데, 인접한 노드를 모두 탐색하는 것은 BFS이므로 BFS를 사용하면 될 것 같다고 생각했다. 하지만 이번 문제 역시 막힌 부분이 있었는데, 입력으로 익은 토마토가 1개 주어질 경우는 구현이 됐지만, 익은 토마토가 2개 이상 주어지면 답이 이상해졌다. 역시 다른 블로그 분들의 글을 보고 힌트를 얻을 수 있었다. -해법 위에서 언급한 문제점이 발생된 이유는 초기 인자를 넘겨줄 때 모든 칸을 탐색..

→2020.11.13

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2178] 미로 탐색(JAVA 구현,추가풀이)

-내 생각 알고리즘 공부를 시작하고 코딩 테스트에서 자주 나온다는 최단경로 문제를 처음으로 풀어보았는데.. 이전에 여러 글들을 보면서 최단거리 문제의 경우에는 BFS만을 이용해서 풀 수 있다고 알고 있었기 때문에 BFS를 사용하려고 했지만, 어떻게 구현해야 할지 감이 잡히지 않았다. 기본적인 흐름은 앞선 DFS문제들과 마찬가지로 인접한 좌표를 탐색하는 것부터 시작해야 한다고 생각했고, 각 경로마다 이동할 때마다 카운트해주어서 분기점에서 갈라진 경로마다의 카운트 변수를 비교해 최솟값을 찾으려고 했는데, 이것도 생각만 했지 구현도 완벽하게 하지 못했다. 2시간 정도 고민해보고 도저히 안될 것 같아 다른 여러 블로그들을 참고했는데, 하단의 Idgeao99님 블로그에서 힌트를 얻을 수 있었다. 혹시라도 막히는 ..

→2020.11.12

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1012] 유기농 배추(JAVA 구현,추가풀이)

-내 생각 DFS, BFS 분류가 되어있는 유기농 배추 문제이다. 문제 자체는 백준 2667 단지 번호 붙이기와 다르게 보이지만, 사실상 같은 문제라고 생각했다. 단지 번호 붙이기 같은 경우에는 인접한 아파트의 수를 카운트하는 것이라면, 이 문제는 인접한 배추의 묶음단위를 카운트하는 것이었다. 그렇기 때문에 DFS를 이용해 깊이를 우선하여 완전 탐색을 실시해 풀 수 있다고 생각했다. -해법 코드의 내용은 단지번호 붙이기에서 약간만 수정해주면 된다. import java.util.*; public class Main { static int node[][]; // 배추밭 배열 static int check[][]; // 배추방문 배열 static int cnt =0; // 배추의 묶음을 카운트 할 변수 st..

→2020.11.12

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2667] 단지번호붙이기(JAVA 구현,추가풀이)

-내 생각 DFS, BFS카테고리에 분류되어 있는 문제인 단지 번호 붙이기이다. 이제 막 DFS, BFS를 공부하기 시작한 입장에서 이게 어떻게 하면 DFS와 BFS를 이용하여 풀 수 있는 거지..?라는 생각이 들었다. 아마도 응용력이 많이 부족한 듯싶다. 그래서 다른 블로그 분들의 풀이를 한 번 분석해봤는데, 대다수가 주석처리가 많이 되어있지 않아 이해하는데 어려움이 많았다. 그래서 일단 되는데 까지 해보자 했는데 진짜 됐다.. 기분 좋아 ㅎㅎ -해법 이 문제 같은 경우에는 한 칸에 1이 존재한다면 주변에 1의 수만큼 카운트를 올려준 후 별도의 공간에 저장 후 오름차순 출력을 하면 되는데, 문제는 주변에 1의 수를 어떻게 셀 것인가가 관건이었다. 개인적인 생각으로는 내가 푼 방법이 DFS인지는 모르겠지..

→2020.11.12

티스토리툴바