728x90 전체 글206 [BOJ/백준] 16929 Two Dots ● [문제번호 16929] Two Dots https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net ● 알아야 할 것 : DFS (재귀) ● 풀이 과정 : 문제를 읽고 첫번째로 생각난 풀이는 DFS (재귀)를 이용하여 모든 점을 시작점으로 확인하는데 사이클이 완성되는 경우는 시작점에서 최소 4개의 점을 방문하여 다시 시작점으로 돌아오는 것이다. 예제도 맞고 방문순서나 로직에는 문제가 없는 거 같지만 계속 1%에서 틀려서 (결국 틀리는 원인은 Y.. 2021. 9. 13. [BOJ/백준] 7562 나이트의 이동 ● [문제번호 7562] 나이트의 이동 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ● 알아야 할 것 : BFS : pair 자료구조와 메소드 : queue 자료구조와 메소드 ● 풀이 과정 : BFS를 이용하여 구현했다. 체스판에서 다음 위치로 이동 불가능한 경우는 다음과 같다. 1. 체스판의 X축을 벗어나는 경우 2. 체스판의 Y축을 벗어나는 경우 3. 방문한 적이 있지만 최소 거리가 아닌 경우 : DFS도 구현했지만 '시간 초과'를 벗어나.. 2021. 9. 13. [BOJ/백준] 7576 토마토 ● [문제번호 7576] 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ● 알아야 할 것 : BFS : pair 자료구조와 메소드 : queue 자료구조와 메소드 ● 풀이 과정 : BFS를 이용하여 구현했다. 토마토가 들어 있는 상자(이하 토마토 지도)에서 다음 토마토 위치로 이동 불가능한 경우는 다음과 같다. 1. 토마토 지도의 X축을 벗어나는 경우 2. 토마토 지도의 Y축을 벗어나는 경우 3. 방문한 적이 있지만 기.. 2021. 9. 13. [BOJ/백준] 2178 미로 탐색 ● [문제번호 2178] 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ● 알아야 할 것 : vector 자료구조와 메소드 : pair 자료구조와 메소드 : BFS : DFS (재귀, 비재귀) ● 풀이 과정 : 보통 visited 배열원소에 bool값으로 방문여부를 저장했다면 이 문제에서는 (1, 1)부터 현재 위치까지 최단 거리를 저장한다. : BFS, DFS (비재귀)로 구현하면 미로의 좌표를 이용해서 구현해야하므로 pair 자료구조를 이용한다. : BFS, .. 2021. 9. 13. [BOJ/백준] 4963 섬의 개수 ● [문제번호 4963] 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ● 알아야 할 것 : vector 자료구조와 메소드 : pair 자료구조와 메소드 : BFS : DFS (재귀, 비재귀) ● 풀이 과정 : [2667 단지번호붙이기] 문제에서 각 섬(단지)의 육지(집)의 갯수를 세는 부분을 빼고 이어지는 조건(가로, 세로)에 대각선까지 추가한 것이다. 체감상 더 [4963 섬의 개수]가 더 쉬운 것 같다. : BFS, DF.. 2021. 9. 13. [BOJ/백준] 2667 단지번호붙이기 ● [문제번호 2667] 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ● 알아야 할 것 : vector 자료구조와 메소드 : pair 자료구조와 메소드 : BFS : DFS (재귀, 비재귀) ● 풀이 과정 : BFS, DFS (비재귀)를 구현하면 집이 있는 좌표를 이용해서 구현해야하므로 pair 자료구조를 이용한다. main문 1. 모든 집을 확인하는데 2. 방문한 적 없거나, 지도에 집이 있다면 3. 방문 체크인 4. 함수 진.. 2021. 9. 13. 이전 1 ··· 8 9 10 11 12 13 14 ··· 35 다음 728x90
