조준화의 오류정정

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번: 벽 부수고..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 예제 5 17 res : 2 처음에 떠올린 풀이는 순간 이동이 한 번에 한 번만 가능한 줄 알고 +- 한 칸과 순간이동 한 것까지 큐에 넣어서 bfs를 돌렸다. 이렇게 구현하면 주의점이 방문 조건을 체크할 때 이미 방문한 것도 다시 방문해서 최단거리로 체크해야 했다. 이 부분 때문에 틀리는 줄 알고 찾아보니 가중치가 0, 1 밖에 없는 그래프 탐색을 위한 0-1 BFS 알고리즘이 있었는데, 내가 구현한 것과 얼추 비슷해서 맞는..

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 예제 10 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ans : 3 먼저 bfs를 통해 섬에 번호를 매겨줄 필요성을 느꼈다. 어떤 풀이를 쓰던 무조건 섬끼리..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 예제 5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2 0 0 7 6 2 4 0 0 0 0 0 0 0 0 0 ans : 2 가장 먼저 떠올릴 수 있는 풀이는 1년 후 빙산의 형태로 바꾸고 바꿀 때마다 BFS를 돌리는 방법이다. 이 방식으로 했을 때 구현은 쉬워 보이지만 시간 복잡도가 문제가 된다. 위의 방식대로 시간 복잡도를 계산해 보자. 최대 300 * 300 크기의 배열에 빙산이 높이 10까지 있을 수 있다. 300 * 30..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 예제 6 4 0100 1110 1000 0000 0111 0000 15 4 4 0111 1111 1111 1110 ans : -1 처음에는 BFS를 하는데, dist를 pair로 해서 방문가능하지 판단할 때 if(dist.second) >= 2 continue; 이런 느낌으로 한 번 부수면 계속 그 사실을 기억하는 식으로 풀이를 짰다. 그러나 pair로 구현하면 구현이 굉..