BFS5 백준 [자바 java] 14904 : 쉬운 최단거리 https://www.acmicpc.net/problem/14940지도가 주어지고 각 위치마다 목표지점까지 얼마나 걸리는지를 출력하는 문제이다.우선 bfs를 이용한 문제라는건 인식했다!그래서 처음에는 각 계층마다 cnt값을 넣어주는 방식으로 답을 정의했는데 생각해보니까 이 문제는 각 위치마다의 값을 저장하는 문제이기 때문에 그냥 그 시점에 해당 노드 값에 1을 더한 값을 넣어주면 되는 것이었다. 핵심 개념for(int i = 0;i우선 입력을 받다가 2를 만나면 여기가 도착지점이므로 이 노드를 큐에 넣는다. int[] dx = {0,1,0,-1};int[] dy = {1,0,-1,0}; while(q.size() != 0){ xy now = q.poll(); for(int k = 0;k= 0.. 2025. 6. 25. 백준[자바 java] 17086 : 아기상어 2 https://www.acmicpc.net/problem/17086오래전에 풀었던 문제인데 쉬운 문제부터 다시 감잡으려고 풀었다. bfs로 각 격자 중 아기상어로부터 가장 멀리 떨어져있는 격자의 거리를 구하는 문제이다. 이 문제에서는 위, 아래, 양 옆, 대각선 총 8개의 격자를 탐색해야했다.이를 하나하나 코드화하기는 지저분하고 힘드니까 dx,dy테크닉을 사용하였다. 또한 한번 방문한 격자는 다시 방문하는 것은 메모리, 시간 낭비이므로 vis배열을 이용하여 중복탐지를 하였다. bfs의 사이클을 탐지하기 위해서 x,y값이 -1인 값을 매 사이클이 시작할 때마다 넣었다.만약 방금 poll 한 값이 -1이라면 이건 사이클이 한번 돌았다는 이야기이므로, 거리를 하나 더해주고, 새로운 (-1,-1)객체를 큐에 넣.. 2025. 6. 24. 코드트리 [자바 java] 최소 경로로 탈출하기 https://www.codetree.ai/missions/2/problems/escape-with-min-distance?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이전에 풀었던 네방향 탈출하기 문제와 유사하다. 하지만 다른 점이 있다면 도착까지 거쳐온 칸수를 세야한다는 점이다. 이 문제는 dfs보다는 bfs로 푸는 것이 좋은데 그 이유는 bfs는 경로를 탐색하다가 가장 빨리 도착점을 발견한 시점이 최소거리이지만, dfs는 도착점을 발견했더라도, 그 경로가 최소인지 알기 위해서는.. 2023. 8. 10. 코드트리 [자바 java] 네 방향 탈출 가능 여부 판별하기 https://www.codetree.ai/missions/2/problems/determine-escapableness-with-4-ways?utm_source=clipboard&utm_medium=text https://ethereal-coder.tistory.com/86 코드트리 [자바 java] 두 방향 탈출 가능 여부 판별하기 https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보 ethereal-coder.tistory.com 두방향 탈출여부 .. 2023. 8. 1. 백준 [자바 java] 7576번 : 토마토 처음 봤을 때에는 평소에 많이 봤던 문제인 것 같아서 쉽다고 생각했는데 시간 초과가 나서 조금 헷갈렸다. import java.util.*; import java.io.*; class Main{ static int n; static int m; static int[][] arr; static int k = 0; static int ok() { int ok = 1; for(int i = k;i 2022. 8. 19. 이전 1 다음
