Henzee's Archive

문제 링크 문제 분석학생들 사이의 사이클을 발견한 뒤 방문 기록을 통해 중복 방문을 방지하고 사이클에 속하지 않은 학생 수를 출력하는 문제입니다.백준에서는 DFS 문제로 카테고리가 분류되었는데 저는 바킹독 님의 알고리즘을 따라 BFS 개념으로 문제를 풀었습니다.시간 복잡도는 O(N) 입니다. 문제 풀이 각 노드를 따라가며 사이클을 찾습니다.탐색 중 state[cur] == x 인 경우는 현재 탐색에서 사이클이 발생한 것으로 간주해 사이클에 포함되는 노드를 마킹(state[cur] = CYCLE_IN) 합니다. 이미 방문한 노드인 경우(state[cur] != 0) 탐색을 종료합니다. 최종 제출 코드 #include #include #include #include #include #incl..

문제 링크     문제 분석도화지에 1로 연결된 그림의 개수를 찾고 가장 넓은 넓이를 출력하는 전형적인 DFS/BFS 문제이다.상,하,좌,우로 연결된 부분만 그림으로 간주하고, 대각선에 있는 것은 떨어진 그림으로 간주한다.또한, 그림의 넓이는 1의 개수를 말하며 그림이 하나도 없는 경우에 가장 넓은 넓이로 0을 출력하면 된다.   문제 풀이 DFS로 탐색 시 현재 그림의 개수를 저장하는 방법에서 틀리고, 수정한 뒤에 최종 코드를 작성했다. 1. 방문 여부와 1인지 확인2. 탐색 전 그림의 넓이 변수를 0으로 초기화3. DFS 탐색 시작4. 방문 처리 및 그림의 넓이 증가5. 사방탐색으로 갈 수 있는 곳을 방문 처리6. DFS 탐색 후 그림의 개수를 증가시키고 가장 넓은 그림 갱신    최종 제출 코드 #..

문제 링크     문제 분석R×C 크기의 보드에 알파벳이 하나씩 적혀있다. (1, 1)부터 시작해서 같은 알파벳을 지나지 않고, 최대로 지날 수 있는 칸 수를 구하는 문제이다.말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동할 수 있고 (1, 1)도 칸 수에 포함한다.   문제 풀이 DFS를 사용해서 사방탐색을 하고, 지나온 알파벳을 저장해 중복 방문하지 않도록 체크한다.중요한 점은 한 방향으로 탐색을 마친 뒤 지나온 알파벳을 초기화해줘야 한다는 점이다. 만약, 예제 입력 2에서H → F → D 순서로 탐색을 했다면, 탐색을 마친 뒤 방문한 알파벳들의 방문 처리를 초기화해줘야 한다. 그래야 새로운 루트인 H → A → J → G 의 방문 처리를 제대로 할 수 있다.  자세한 구현 사항은 코드를 통해 알아..

백준 15686번 - 치킨 배달 (골드 5)     문제 분석최대 M개의 치킨집을 골라 도시의 치킨 거리의 최소값을 구하는 문제이다.조합을 이용해서 전체 치킨집 개수 중에 M개의 치킨집을 골라야 한다. (최대 M개라고 했으니, M개를 고르는 것이 치킨 거리의 최소값을 구할 선택지가 많아지므로)고른 치킨집을 가지고 각 집마다 치킨 거리(집과 치킨집의 최소 거리)를 구해준다.치킨 거리의 핪의 최소값을 구해준다. (= 도시의 치킨 거리의 최소값) 백트래킹 (Backtracking)M개의 치킨집을 고를 때 사용하는 조합은 백트래킹을 이용해서 구현할 수 있다.백트래킹은 현재 상태에서 가능한 모든 선택지를 탐색하는 알고리즘이다.재귀 함수로 구현할 수 있으며 탐색을 들어가서 원하는 값이 아닌 경우 이전 탐색지로 돌아..

백준 2468번 - 안전 영역 (실버 1)     문제 분석비의 양에 따라 물에 잠기지 않는 안전 영역의 최대 개수를 출력하는 문제이다. 풀이 과정DFS 를 이용해서 풀어야겠다고 생각했으나, 비의 양을 조절하는 것과 잠긴 지역을 어떻게 표시해줘야 할 지 고민했다.문제 마지막에 "아무 지역도 물에 잠기지 않을 수도 있다."는 조건이 있었으므로 비의 높이는 아무 지역도 물에 안 잠기는 0부터 지역의 최대 높이까지로 설정해줬다.잠긴 지역을 표시하는 방법은 방문 배열에서 잠긴 지역의 방문 처리를 해주는 것이다. 알고리즘 정리비의 높이가 k일 때, 잠긴 지역 표시하기 (비의 높이 k는 0부터 지역의 최대 높이까지) DFS 탐색으로 연결된 지역 탐색 후 안전 영역 개수 저장안전 영역 개수의 최대값 저장  최종 제출..

백준 2178번 - 미로 탐색 (실버 1)     문제 분석전형적인 BFS 탐색을 통한 최단 거리 구하기 문제이다. 알고리즘큐에 시작 위치와 이동한 칸 수를 저장한다.큐에서 빼낸 뒤 도착 위치인지 확인한다.도착 위치가 맞다면 이동한 칸 수 출력 후 탐색을 종료한다.사방 탐색으로 이동할 수 있는 위치인지 확인 후 해당 위치와 이동한 칸 수를 큐에 저장한다.큐가 빌 때까지 위의 내용을 반복한다. 주의 사항입력 시 각각의 수가 붙어서 주어지므로 string으로 입력 받아서 각 문자를 정수로 변환해줘야 한다.칸을 셀 때 시작 위치 포함이므로 칸 수에 1부터 넣어줘야 한다.시작 위치를 (0, 0) 부터 하므로 도착 위치가 (N-1, M-1) 이어야 한다.델타 배열을 사용해 상, 하, 좌, 우로 사방 탐색을 진행한..

백준 2573번 - 빙산 (골드 4)     문제 분석주어진 빙산의 높이 정보를 가지고 매 년마다 빙산이 녹으면 몇년 후 최초로 빙산이 2개 이상으로 분리되는지 찾는 문제이다. 만약, 모두 다 녹을 때까지 분리되지 않으면 0을 출력한다.먼저 큰 로직 두 개를 세우고 구현했다.첫 번째, 빙산을 녹이는 작업 : DFS로 구현두 번째, 빙산이 분리됐는지 확인하는 작업 : DFS로 구현 처음 시도코드를 작성하면서도 반복문을 실행할 때마다 방문 배열을 초기화해주는 것이 비효율적이라고 생각했다. 그리고 DFS() 메서드에서 종료 조건이 어떤 것인지 몰라서 x == M && y == N으로 해주었는데, 이 부분도 미심쩍었다. 아니나 다를까 틀렸습니다...#include #include using namespace s..

백준 1707번 - 이분 그래프 (골드 4)     문제 분석주어진 그래프가 이분 그래프인지 판별해내는 문제이다.DFS나 BFS로 주어진 그래프를 탐색하며 정답을 구할 수 있다. 이분 그래프그래프의 모든 정점을 두 가지 색상으로만 칠할 수 있다.같은 색상의 정점은 간선으로 연결되면 안 된다.만약 같은 색상의 정점이 간선으로 연결되어 있다면? 이분 그래프 아님 알고리즘 작성인접 행렬에 그래프의 연결 정보를 저장(양방향 연결이므로 행, 열 모두 1로 저장)큐에 시작 노드를 넣고 색상 배열의 시작 노드 인덱스에 1 저장큐에서 꺼낸 노드의 인접 노드를 큐에 넣고 색상 배열의 인접 노드 인덱스에 이전 노드의 값 ×-1 저장 (-1과 1로 색상 구분)만약 큐에서 꺼낸 노드의 색상 정보와 인접 노드의 색상 정보가 같..

백준 2667번 - 단지번호붙이기 (실버 1)     문제 분석N * N 크기의 지도를 입력받아 대각선을 제외하고 상,하,좌,우로 연결된 집의 모임의 개수와 해당 모임의 집의 개수를 출력하는 문제이다.2차원 벡터에 입력을 저장하고 (0, 0)부터 DFS로 사방 탐색을 하며 단지의 개수와 단지에 속한 집의 개수를 카운트해야겠다고 생각했다.델타 배열을 사용해서 상,하,좌,우에 집이 있는지 확인하고 해당 인덱스가 유효 범위인지 확인 후 DFS 탐색을 해야겠다고 생각했다. 처음 시도2차원 벡터에 지도의 정보를 저장하고 방문하지 않은 집의 위치에서 DFS 탐색을 시작해 단지의 개수를 출력하려고 했으나, 입력 오류와 단지에 속한 집의 개수를 세지 못했다. 원인 분석입력을 받는 과정에서 숫자를 바로 입력받는다고 생각..

백준 1260번 - DFS와 BFS (실버 2)       이 문제를 풀기 위해서는 그래프 탐색에 대해 알아야 한다. 그래프 탐색이란?하나의 정점에서 시작해 차례대로 모든 노드를 방문하는 것그래프 탐색의 방법깊이 우선 탐색 (Depth First Search, DFS)너비 우선 탐색 (Breadth First Search, BFS)그래프 탐색의 두 가지 방법인깊이 우선 탐색 (Depth First Search, DFS)과 너비 우선 탐색 (Breadth First Search, BFS)에 대해 알아보자.  DFS(Depth First Search)란?깊이 우선 탐색시작 지점에서 출발하여 한 방향으로 탐색탐색을 더이상 할 수 없으면 마지막 만난 지점으로 돌아와 다른 방향으로 다시 탐색후입 선출(LIFO :..