'📜 코딩테스트/BAEKJOON\BFS, DFS' 카테고리의 글 목록

백준 9466번 : 텀 프로젝트 (JAVA) 문제 풀이

2021.07.08

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ✏️ 문제 🔐 문제 해결 이 문제는 생각보다 간단한데 어렵다. 위 예제 중 하나를 그림으로 표현해보았다. 그림을 보면, (1번, 5번) -> 3번 과 팀을 이루고 싶어한다. 하지만 3번은 혼자 팀을 하길 원한다. 이렇게 되면 1번 5번은 팀을 이룰 수 없게 된다. 또, 2번-> 1번 -> 3번(혼자 팀) 이므로 2번도 팀을 이룰 수 없게 된다. 4번, 6번, 7번은 서로를 가리키고 있으므로 팀이 완성이..

📜 코딩테스트/BAEKJOON\BFS, DFS

백준 2206번 : 벽 부수고 이동하기 (JAVA) 문제 풀이

2021.07.07

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net ✏️ 문제 🔐 문제 해결 예를들어 아래와 같은 5X5 배열이 있다고 해보자 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 그림으로 표시하면 아래와 같을 것이다. 화살표 방향과 같이 시작점(0,0) 에서는 두 가지 방향으로 갈 수 있을 것이다. 하지만 1번으로 벽을 뚫고 간다면, 아래의 문제점에 부딪히게 된다. 도착지점으로 가기 위..

📜 코딩테스트/BAEKJOON\BFS, DFS

백준 7569번 : 토마토 (JAVA) 문제 풀이

2021.06.26

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이 문제는 이전의 풀었던 7576번 토마토와 비슷한 문제이다. 이 문제에서의 다른 점은 토마토가 2차원 배열에 담기는게 아니라, 3차원 배열에 담기기 때문에 상,하,좌,우,앞,뒤까지 총 6번을 체크해줘야한다. ✏️ 문제 🔐 문제 해결 어려울 것이 없다. 이전과 동일한 방식으로 처리할 것이고, 그저 체크해야 할 곳이 2곳이 늘었다는 점 외에는 말이다. 토마토를 담기 위한 3차..

📜 코딩테스트/BAEKJOON\BFS, DFS

백준 7576번 : 토마토 (JAVA) 문제 풀이

2021.06.24

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ✏️ 문제 🔐 문제 해결 이 문제는 미로 탐색 문제처럼 풀면 된다. 대신 이 문제에서 주의해야할 점은 미로 탐색 문제처럼 한곳에서 출발하는게 아니라, 시작점이 여러지점이라는 점이다. 이것 때문에 머리 아팠는데 생각해보면 그리 어렵지 않다. 아래 코드를 보면서 살펴보자. int[][] days = new int[N][M]; int[][] tomatos = new int[N][M]; ..

📜 코딩테스트/BAEKJOON\BFS, DFS

백준 2178번 : 미로 탐색 (JAVA) 문제 풀이

2021.06.24

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 이 문제는 이전의 풀었던, 그림 문제처럼 풀면 안된다. 이전 문제처럼 풀게 되면 최단거리를 구하지 못한다. 그래서 이 문제는 시작지점(0,0)으로 부터의 모든 칸의 거리를 계산하여 또 다른 배열에 저장을 할 것이다. 이게 무슨 말이냐면, 아래 그림을 보면 우리가 구해야 하는 경로는 빨간색 경로인데, 어떻게 구하냐면 위에서 말했듯이 시작점으로부터의 거리를 계산한 배열을 생성해줄것이다. int[][] dis..

📜 코딩테스트/BAEKJOON\BFS, DFS

백준 1926번 : 그림 (JAVA) 문제 풀이

2021.06.23

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BFS의 개념을 가장 잘 이해할 수 있는 문제라고 할 수 있다. 차근차근 한번 풀어보도록 하자. ✏️ 문제 🔐 문제 해결 값이 1이면 색칠이 된 부분이니까, 모든 그림을 전부 돌면서 1이거나 방문하지 않은 그림을 체크하면서 처리해주면 될 것 같다. 우선 모든 그림을 2차원 배열에 담아주도록 한다. (StringTokenizer를 이용해서 각각 원소를 넣어준다.) arr = new int[n][m]; /..

백준 9466번 : 텀 프로젝트 (JAVA) 문제 풀이

백준 2206번 : 벽 부수고 이동하기 (JAVA) 문제 풀이

백준 7569번 : 토마토 (JAVA) 문제 풀이

백준 7576번 : 토마토 (JAVA) 문제 풀이

백준 2178번 : 미로 탐색 (JAVA) 문제 풀이

백준 1926번 : 그림 (JAVA) 문제 풀이

티스토리툴바