[백준,BOJ 2206] 벽 부수고 이동하기(JAVA 구현,추가풀이)

-내 생각 너무 어렵다... 이전까지 문제들을 풀어보면서 너무 자만했나 보다. 문제 자체는 이해가 가는데 구현을 못하겠다 ㅠㅠ 티스토리 규글님 블로그의 코드를 참고했는데, 솔직히 이해 안 가는 부분이 있어서 반복해서 봐야 할 것 같다... https://kim6394.tistory.com/201 [백준 2206] 벽 부수고 이동하기 (Java, BFS) [백준 2206] 벽 부수고 이동하기 (Java, BFS) 문제 출처 : 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳.. kim6394.tistory.com import java.util.*; class xy{ int x; int y; int z..

→2020.11.16

코테/백준 온라인 저지(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

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

[백준,BOJ 1260] DFS와 BFS(JAVA 구현, 재풀이)

-풀이 이전에 풀이했던 DFS, BFS문제는 그래프의 구현을 위해 인접 행렬을 사용한 경험이 있었기 때문에, 이번에는 인접 리스트로 그래프를 구현해 풀어보고자 했다. import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { // DFS 메소드 static void dfs(ArrayList a, boolean[] check, int v) { if(check[v] == true) return; // 재귀호출 종료 부, 방문한 적이 있으면 메소드 종료 che..

→2020.11.11

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

[백준,BOJ 1181] 단어 정렬(JAVA 구현)

-풀이 이 문제의 경우 역시 좌표 정렬하기 문제와 마찬가지로 Comparator 인터페이스의 compare 메서드를 재정의해 비교하여 정렬하면 되는 문제이다. 다만 주의해야 할 점은 동일한 단어가 등장할 경우 한 번만 출력해야 한다는 점이다. import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String arr[] = new String[n]; // 문자열 배열에 데이터 저장 for(int i =0;i

→2020.11.10

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

[백준,BOJ 1427] 소트인사이드(JAVA 구현,재풀이)

이 문제 역시 이전에 풀어보았던 문제로 이전에는 정수로 데이터를 입력받은 뒤 수학적으로 각 자릿수를 추출하였지만, 이번에는 String 타입으로 데이터를 다루어 보았다. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // 데이터 입력 ArrayList arr = new ArrayList(); // String타입의 데이터를 문자형으로 저장 할 arrayList for(int i =0;i=0;i--) { ..

→2020.11.10

티스토리툴바