본문 바로가기

BFS4

[Day12]JAVA- 백준 토마토 (7569번) BFS 활용 https://www.acmicpc.net/problem/7569 백준 7569번 문제는 BFS 를 활용해서 풀 수 있다. 3차원 배열이 나와서 당황할 수 있지만 침착하게 문제의 규칙을 찾으면 된다.  여기서 규칙은 토마토가 상, 하 , 좌 , 우 , 앞, 뒤 로 영향을 준다는 것이다. 3차원 배열이여서 이해가 어려울 수 있는데 콘서트 장이라고 생각해보면 상,하(H) 는 1층,2층..  을 나타내는 것이고 좌,우(M) 는 양 옆 을 나타내는 것이고 , 2차원에서는 열이라고 한다. 앞,뒤(N) 는 앞줄 , 뒷줄을 나타내는 것이고, 2차원에서는 행이라고 한다.  콘서트장 가면 어떻게 앉는가? 1층 앞줄부터 하나씩 앉지 않는다.  쉽게 생각해서 1층 앞줄 부터 자리를 채워간다고 생각하면 된다.  *혼자 힘으로.. 2024. 11. 9.
[Day11]JAVA- 백준 Yes or yes (25195번) DFS,BFS 활용 https://www.acmicpc.net/problem/25195 25195번 문제는 BFS , DFS 둘다 활용해서 풀 수 있다. https://h0wever.tistory.com/6 [알고리즘] DFS (깊이 우선 탐색) 이해DFS(Depth-First Search , 깊이 우선 탐색)- 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘 - 반복물을 활용하거나 재귀문을 통해서 구현된다 장점 :  현재h0wever.tistory.com 주의해야 하는 것은 단방향이고 , 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 하나라도 존재한다면 "yes" 이다. DFS 방식을 이용한다면 4가지 경우를 고려해야한다.  처음 1 정점에 곰곰이 팬들이 있는 경우 -> 그 다음 어디로 .. 2024. 11. 8.
[Day10]JAVA- 백준 특정 거리의 도시 찾기 (18352번) https://www.acmicpc.net/problem/18352  백준 18352번 문제를 풀기위해서는 BFS 에 대해서 알아야 한다. BFS 에 대해서 잘 알고 있으면 어려운 문제는 아니지만 , 함정이 있다! 문제를 꼼꼼히 읽어야 한다.BFS,DFS 문제를 많이 풀다보면은 어느정도 문제를 읽다보면 어떠한 알고리즘을 사용해야겠다 감이 잡힌다. 그래서 대강 문제를 읽보 바로 풀어버리는 실수를 하게 되는것이다. 이 문제에서 포인트는 단방향의 도로인것과 , 도시의 번호를 오름차순으로 출력하는 것이다.보통을 노드 사이는 양방향인 경우가 많아 아래와 같이 선언해 주는 경우가 많다. graph.get(u).add(v);grpah.get(v).add(u); 단방향은 한방향으로만 선언해 줘야 한다!graph.get.. 2024. 11. 6.
[Day09]JAVA- 백준 나이트의 이동 (7562번) https://www.acmicpc.net/problem/7562  백준 7562번 문제를 풀기위해서는 BFS 를 활용해야한다.  사실 DFS는 문제를 풀기위한 수식의 일뿐 문제를 이해하고 어떤 방식으로 체크판에 나이트가 움직이는 지를 파악하는게 중요하다. 체스판에서 나이트가 움직일 수 있는 경우는 총 8가지 이다.  체크판을 벗어나지 않으면서 이동 할 수 있는 모든 경우를 구하여 그 중 나이트가 이동하고자 하는 판 까지의 이동만 계산하면 된다.   행 , 열 을 구분하여 이동할 수 있도록 배열에 8가지 경우를 담은 배열을 생성한다. static int x[] = {-2, -2, -1, 1, 2, 2, 1, -1};static int y[] = {-1, 1, 2, 2, 1, -1, -2, -2}; 이동한.. 2024. 11. 5.

티스토리툴바