본문 바로가기

깊이우선탐색

(5)
[백준] 10026 - 적록색약 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 위 문제는 순수 BFS(너비우선 탐색)와 DFS(깊이우선탐색) 두가지 모두로 해결이 가능하다. 색약의 경우만 R, G중 하나를 R 혹은 G로 모두 변경 후에 다시 BFS, DFS를 돌리면 색상의 구역을 구분할 수 있다. 아래 코드는 BFS, DFS 모두를 구현한 정답이다. 직장내 SW 검정이 있어 멘토링을 하느라 두가지 방식 모두 구현하였다. 아래 코드에서 관심있게 볼 포인트는 BFS는 Queue, DF..
[백준] 2573 - 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net DFS(깊이우선탐색) 응용문제다. 섬의 얼음을 녹인 후에 빙산이 둘로 쪼개졌는지를 알아내기 위해 DFS를 쓰는데, 사실 DFS말고 BFS(깊이우선탐색)으로도 풀이가 가능하다. 주의할 점은 1년이 지나 빙산의 얼음을 녹일때, 다른 copy_map을 만들어서 녹은 빙산의 지도를 만들어야지, 기존 map에서 그냥 주변 0의 갯수만큼 차감하다보면, 이전에 차감해서 0이된 지역을 오인해서 과다차감을 하게될 수 있다..
[백준] 1987 - 알파벳 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 순수하게 DFS(깊이우선탐색)만으로 풀수 있는 문제이며, 아마 가장 흔하게 나오는 깊이우선탐색의 유형일 것 같다. 주의할 점은 탐색을 하면서 이미 한번 지나간 알파벳에 대해서 방문 여부를 관리해야 하는데, 깊이우선 탐색 전에 방문 상태를 true로.. 탐색을 마치고 재귀호출에서 빠져 나왔을때는 다음 경로 계산을 위해 방문 여부 상태를 false로 되돌려 주어야 한다. #include int R, C; i..
[백준] 1103 - 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제에서 제시하는 map의 사이즈가 최대 50x50이라 시간초과가 날 일은 없을 것이라 생각하고, DFS(깊이우선 탐색)을 통한 완전 탐색을 하면 될 줄 알았다. 그런데 문제를 다시 읽어보니 말을 움직이는데 있어 중간에 사이클이 생길 수 있네? 사이클에 대해서는 같은 map 사이즈로 visited 배열을 선언해서 이전에 방문한 적이 있으면 -1을 출력 후 리턴을 하게 해주었는데, 같은 위치를 가더..
[백준] 1062 - 가르침 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 처음엔 좀 쉽게 생각했다. ASCII 코드에 대한 이해도와 입력되는 문자열에서 나타나는 알파벳의 발생 횟수를 기억해놓고 이를 내림차순으로 정렬하면 배우는 글자 수에 따라 읽을 수 있는 단어 갯수를 알아낼 줄 알았다. 그런데 해보니까 아니네... 이번 문제에서 필요한 지식은 이정도가 될것 같다. ASCII 코드에 대한 이해를 통해 알파벳 별 출현 여부를 bit masking하여 배열에 저장하..