ETC/Algorithm
-
[백준/JAVA] 2206 벽 부수고 이동하기ETC/Algorithm 2023. 5. 27. 01:45
문제 문제 인식 변수 상황 N * M의 행렬로 표현되는 맵이 있고, 0은 이동가능 1은 이동 불가능한 벽으로 표현된다. 이동은 (1,1)에서 시작하며, 도착점은 (N,M)으로 고정되어있다. 하지만 변수 상황이 주어지는데 간단히 기존 BFS 문제에서 벽을 한번은 통과할 수 있다는 것이다. 그렇다면 다른 BFS 문제와 형태는 같지만 벽을 한 번 통과 가능하다는 점을 어떻게 구현할 것인가가 문제의 핵심으로 인식했다. 실패한 문제 해결 처음 생각한 방법은, BFS를 재귀를 통해 다시 불러오는 방식을 생각하였다. 첫 시작은 벽 부신 값을 false로 갖고 시작 재귀를 통해 한번 벽을 부셨다면 true 값을 주고 반복하여 진행하였다. 여기서 문제가 발생하는데, 벽을 한번 부신 경우가 그냥 정상적인 길로 가도 거리 ..
-
[백준/JAVA] 10828 스택ETC/Algorithm 2023. 5. 26. 17:25
풀이 push의 경우에는 명령어에 입력값을 같이 보낸다. 조건문을 통해 push 명령어일 경우 nextToken()을 한번 더 수행하도록 했다. 각 명령어의 경우를 Switch문을 통해서 처리하였다. Java에서 top을 구현하기 위해서는 Peek을 사용하는데 내용물이 없으면 오류가 발생한다. 따로 조건 추가해야한다. 제출코드 import java.io.*; import java.util.*; class Main { static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { BufferedReader br = ..
-
[백준/JAVA] 10026 적록색약ETC/Algorithm 2023. 5. 25. 02:31
조심! 비색약인과 색약인이 보는 지도는 같지만, 인식하는 내용은 다르다. -> BFS 알고리즘의 조건이 다르다 지도의 R과 G는 같이 있으면 동일한 값으로 취급하지만, 따로 있을 경우 다른 값으로 인식한다. 풀이 DFS를 사용하여 풀었다. 비색약인과 색약인이 인식하는 내용이 다르므로, 알고리즘의 visited의 값은 차이를 갖는다. 고로 변수를 따로 사용한다. 색약인의 경우 다음 좌표의 색과 현재 좌표의 색이 서로 R과G일 때 이동 가능하다. 제출 코드 import java.io.*; class Main { static int N; static char[][] map; static boolean[][] normalVisited; static boolean[][] blindVisited; static in..
-
[백준/JAVA] 26481 수열과 쿼리 42 - 시간 초과ETC/Algorithm 2023. 5. 25. 02:25
주의 미해결 문제이므로 참고만 할 것 제출 코드 import java.io.*; import java.util.*; class Main { static int N,Q; static int l,r; static int[] arr; static int[] lis; static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringToke..
-
[백준/JAVA] 2667 단지번호붙이기ETC/Algorithm 2023. 5. 25. 02:23
풀이 BFS를 사용하여 풀었다. 아파트 단지의 개수, 각 아파트 단지의 집의 개수를 세어야한다. 아파트 단지의 개수를 세기 위해 bfs 메소드가 실행될 때마다 +1을 진행해준다. 아파트 단지 내의 집의 수를 세기 위해 bfs를 진행하면서 큐의 입출력이 발생한 수만큼 +1을 해준다. 아파트 단지의 개수가 정해져 있지 않기 때문에, ArrayList 자료형을 사용해서 아파트 내의 집 수를 저장해준다. 제출 코드 import java.io.*; import java.util.*; class Main { static int[][] map; static boolean[][] visited; static int N; static Queue q = new LinkedList(); static int[] opsX = ..
-
[백준/JAVA] 7576 토마토ETC/Algorithm 2023. 5. 24. 01:24
조심! 시작점은 한 곳에서만 시작하지 않는다. 익은 토마토는 상하좌우로 사방에 영향을 준다. M은 세로 N은 가로이므로 상자[M][N]으로 2차원 배열을 설정해야한다. 풀이 BFS를 사용하여 풀었다. 큐에 좌료값을 입력하기 위해 Pos라는 클래스를 사용하였다. 시작점은 한 곳만이 아니므로 시작점들을 저장할 start라는 리스트에 저장해두고, BFS 시작할 때 큐에 모두 입력하고 시작한다. BFS 이후에는 상자에 "0" 값이 있으면 안된다. findMax()라는 메소드를 통해 최대값(최장시간)을 구함과 동시에 "0"을 발견하게 되면 찾는것을 중지하고 바로 return한다. 제출 코드 import java.io.*; import java.util.*; class Main { static int[][] map..
-
[백준/JAVA] 2178 미로 탐색ETC/Algorithm 2023. 5. 23. 05:25
미로탐색 풀이 BFS 알고리즘으로 해결하였다. 좌표를 저장하기 위해 Pos라는 객체를 사용하였다. 사방으로 이동 가능한 경우의 수를 고려해서 맨 아래 후기에서 적어둔 연산을 사용하였다. (현재까지 지나온 값) + (다음 지나갈 값) = n + 1 이다. 자연스레 다음으로 이동할 위치에 현재 위치에 다음 이동할 위치의 값을 더해서 저장하면 된다. 목적지는 N,M 고정이다. 지도의 [N-1,M-1] 의 값을 출력하면 가장 최단거리이다. 제출 코드 import java.io.*; import java.util.*; import java.lang.*; class Main { static int[][] map; static int M, N; static Queue q = new LinkedList(); stati..
-
[백준/JAVA] 1012 유기농 배추ETC/Algorithm 2023. 5. 23. 02:06
유기농 배추 백준 1012번 바이러스 문제 링크 풀이 재귀형 DFS 알고리즘 사용했다. 시작은 0,0 에서 시작하고, 일반 배열과 같이 선형 탐색을 진행한다. 하지만 그 좌표값이 1인 경우에는 count값을 1 증가시킨다. 현 위치를 "0" 값으로 바꾼다. 현 위치를 기준으로 동서남북 사방으로 재귀함수를 통해 반복진행한다. 더 이상 재귀함수가 진행되지 않을 경우, 다른 "1" 값을 찾는다. 반복 제출 코드 import java.io.*; import java.util.*; import java.lang.*; class Main { static int[][] arr; static int M, N, K; static StringBuilder sb = new StringBuilder(); public stat..