https://www.acmicpc.net/problem/4803 예제6 31 22 33 46 51 22 33 44 55 66 61 22 31 34 55 66 40 0---ans : Case 1: A forest of 3 trees.Case 2: There is one tree.Case 3: No trees.주어진 그래프에서 트리가 몇 개 존재하는지 판단하는 문제이다.트리의 조건은 사이클이 없는 연결 요소이고 n-1개의 간선으로 이루어져 있고 임의의 두 정점에 대해 경로가 유일하다는 것인데, 이 조건을 이용해서 찾아야 한다.처음에는 연결 요소를 찾고 사이클이 없는지 판단한 뒤 n-1개의 간선으로 이루어져 있고 모든 정점 간 경로가 유일한지 체크하려 했다. 그런데 bfs를 사용해서 연결 요소를 찾다 보니 ..

[바킹독님 블로그 정리 글입니다!] [실전 알고리즘] 0x19강 - 트리이번 시간에는 트리를 다루어봅시다. 바로 본론으로 들어가겠습니다. 특별히 트리에서의 BFS와 DFS를 또 익힐 예정입니다. 저희는 0x16강에서 이진 검색 트리를 배우며 이미 트리라는 개념을 적당blog.encrypted.gg 트리의 기본적인 특성부터 알고 가자면, 트리의 정의는 무방향이면서 사이클이 없는 연결 그래프이다. V개의 정점에 대해 V-1개의 간선을 가지는 사이클이 없는 연결 그래프라고 생각하면 된다. 트리에서의 BFS는 그래프의 BFS와는 조금 다른 의미를 가진다. 그래프의 BFS는 특정 정점에서 연결된 점을 찾는 용도로도 많이 사용되었는데, 트리는 연결 그래프이므로 방문 순서와 부모 배열, depth 배열을 채울 수 있..

14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제가 요구하는 내용들을 그대로 하나씩 구현하면 된다. 딱 봐도 디버깅이 매우 귀찮아 보인다. 천천히 실수가 없게끔 구현해 보자. 톱니바퀴가 4개 고정돼 있고, 최대 100번 회전한다. 한 번의 회전이 일어나면 4개 모두 회전할 수 있는데, 데이터가 매우 적어서 시간복잡도 계산도 안 하고 바로 완전탐색으로 구현했다. 문제의 요구사항은 다음과 같다. 회전시키기 k번째 톱니바퀴를 회전시키려면 그냥 새 배열을 만들어서 회전시킨 결과물을 저장하면 끝이다. 근처 톱니..

11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 예제 ...... ...... ...... ...... ...... ...... ...... ...... .Y.... .YG... RRYG.. RRYGG. ans : 3 먼저 맵의 크기가 72로 매우 작고, 한 번의 연쇄 작용 후 맵을 갱신하지 않고는 다시 연쇄 작용을 하기 매우 힘들다. 따라서 연쇄 작용 후 맵 갱신을 하는 방식으로 기초를 잡았다. 연쇄 작용은 BFS로 빠른 시간 내에 구현할 수 있을 것 같고, 맵 갱신 또한 72개의 데..

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 예제 YYYYY SYSYS YYYYY YSYYS YYYYY ans : 2 처음에는 일반적인 백트래킹으로 접근했다. 어차피 데이터의 크기가 25로 매우 작고 시간은 2초로 여유롭니 모든 점을 시작점으로 두고 O(25) 재귀식을 상하좌우 중 방문할 수 있다면 방문하는 식으로 짜서 백트래킹으로 구현하였다. 이 방법에서 두 가지 문제점을 발견했는데, 사진으로 보는 게 나을 것 같다. 애초에 백트래킹은 재귀식으로 해야한다는 고정관념에 잘못 접근한 것 같다. 차라리 데이터가 ..

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 예제 1 4 4 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 ans : 4 2 5 2 0 0 1 1 0 0 0 1 1 0 ans : -1 이 문제를 풀기 전에 아래의 벽 부수고 이동하기 문제를 꼭 꼭 먼저 푸는 것을 추천한다. 내가 떠올린 풀이가 아래 문제와 99% 비슷하기 때문이다. [BOJ] C++ 2206 벽 부수고 이동하기 - BFS 활용 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고..