728x90 전체 글202 [BOJ/백준] 16940 BFS 스페셜 저지 ● [문제번호 16940] BFS 스페셜 저지 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net ● 알아야 할 것 : // ● 풀이 과정 : // ● 주의 할 것 : // ● 참고 할 것 : // ● 풀이 코드 // ● [백준] - [알고리즘 기초 2/2] - [602 - 그래프 1 (도전)] 문제집 번호 문제 번호 문제 이름 풀이 링크 1 16940 BFS 스페셜 저지 https://pirateturtle.tistory.com/280 2 16964 DFS 스페셜 저지 https://pirateturtle.tistory.com/281 3 2146 다리 만들기 h.. 2021. 9. 13. [BOJ/백준] 16947 서울 지하철 2호선 ● [문제번호 16947] 서울 지하철 2호선 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net ● 알아야 할 것 : vector 자료구조와 메소드 : BFS : DFS (재귀) ● 풀이 과정 : 문제를 보고나서 순환선은 Two Dots 문제처럼 시작역에서 출발하여 최소 3개역 이상 거쳐 다시 시작역으로 돌아오는 경우 순환선으로 알아낼 수 있다고 생각이 들었다. 그런데 지선은 어떻게 알아낼까? 지선임을 알아내는 건 위와.. 2021. 9. 13. [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. 이전 1 ··· 7 8 9 10 11 12 13 ··· 34 다음 728x90
