본문 바로가기
728x90
반응형

java230

[백준/java] 2178번: 미로 탐색 - BFS https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제에서는 고려해야할 것이 현재 노드가 방문한 노드인지 확인하는 로직이 필요하고, 또 현재 노드의 좌표가 도착점 좌표와 같을 때 BFS 탐색을 종료하고 찾은 개수를 출력하면 된다. if(visit[cur.y][cur.x]) continue; visit[cur.y][cur.x] = true; if(cur.y == N -1 && cur.x == M - 1) { cnt = cur.step; return; } 아래는 완성된 소스코드.. 2021. 8. 16.
[백준/java] 2667번 :단지번호붙이기 - BFS https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ※ 문제풀이 이번 문제는 그림(1926)문제와 방법은 똑같고 다만 BFS 탐색할 때 해당 위치가 중복되는지 한번 더 확인해주면 된다. 탐색하는 위치의 방문 여부를 한번 더 해주지 않으면 단지의 개수가 불필요하게 더 늘어나게 된다. 문제가 됐던 부분은 아래와 같다. List complex = new ArrayList(); for (int i = 0; i < N; i++) { for (int j = 0.. 2021. 8. 16.
[백준/java] 7569번 : 토마토(3차원배열) BFS 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ※ 문제풀이 이번 문제는 2차원 배열로 푸는 토마토 문제(7576)와 방법은 똑같고 다만 3차원배열이어서 동서남북 + 위 아래까지 조회를 해주면 된다. 그러면 7576번 토마토와 비교해서 어떤 것이 추가되었는지 확인해보자. 먼저 변수 선언부 static int[][][] map; static boolean[][][] visit; static int M, N, H; static int[][] dx, dy, dh; static class No.. 2021. 8. 15.
[백준/java] 7562번 : 나이트의 이동(체스 나이트의 이동) - BFS https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 토마토 문제처럼 이번 문제도 Queue에 넣는 클래스가 y, x값 말고도 cnt가 하나 더 들어갔다. 이것의 용도는 최단거리를 측정할 때 사용하는 것! 이제 점점 BFS로 순회할 때 최단거리를 계산하는 방법이 조금씩 감이 오는 것 같다. 이 문제에서 int형 이차원 배열이 따로 사용되지는 않았다. 방문하는 곳마다 값을 확인할 필요가 없었기 때문이다. 이 문제를 풀때 오래걸리고 오해했던 것은 도착지로.. 2021. 8. 15.
[백준/java] 7576번 : 토마토 - BFS https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ※ 문제 풀이방식 BFS가 응용된 부분 위주로 설명 드리겠습니다 (1) 우선 dy, dx 배열의 값은 두개의 값들을 함께보면 (1, 0), (0, 1), (-1, 0), (0, -1) 이 순으로 되어있습니다. --> 이것이 의미하는 것은 북 동 남 서 방향으로 방향을 설정하는 것입니다. (2) Node 클래스에 기존에 풀이했던 그림, 섬의 개수, 안전 영역같은 문제들과는 달리 x,.. 2021. 8. 14.
[백준/java] 2468번 : 안전 영역 - BFS https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어렵지도, 그렇다고 그렇게 쉬운문제는 아니었다. 생각보다 놓치기 쉬운 함정들이 있었다. 입력의 마지막 설명 중, " 높이는 1이상 100 이하의 정수이다. " 라는 설명이 있는데, 문제 페이지 맨 마지막 "노트"란을 보면 라고 나와있다. 이것을 고려하지 않는 경우가 더러 있었다고 한다. bfs로 순환하여 탐색하되, 순환의 높이의 시작은 0부터 100까지여야 한다는 것이다. package bfs; impo.. 2021. 8. 14.
728x90
반응형

티스토리툴바