발자취

문제를 잘 읽어보고 오자. https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제는 단순한 그래프 탐색 문제이다. 탐색 방법은 상관없으나, bfs로 풀이하면 가독성이 조금 더 좋은 코드가 되어서 bfs로 풀이했다. 문제 풀이는 탐색한 지점에 대해서는 체크 표시를 해 두고, 모든 좌표에 대해서 탐색을 시작해도 되는 점인지 판별하여 탐색하면 된다. 여기서 다른 문제와의 차이점은 여러 개의 테스트 케이스가 있다는 점과, 4개 방향이 아닌 8개..

문제를 읽어보고 오자. https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제를 읽어 보면 그래프 탐색을 사용하는 문제인 것을 알 수 있다. 하지만 약간 까다로운 점은, 특정 조건의 이동을 특정한 횟수 안에 실행한다는 점이다. 이것에 대한 모든 경우를 세야 할까? 나는 처음에 말처럼 움직인 횟수를 큐에 저장해서 확인해 보았다. 하지만 이러한 방법을 사용하니 방문한 경우에 대해서 오류가 있다는 것을 알게 되었다. 벽 부수기 문제 (..

문제를 잘 읽어보고 오자. www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 이 문제도 평범한 그래프 탐색 문제이다. 주어진 사람들 중에 가장 많은 2-친구를 보유한 사람의 수를 출력하면 된다. 문제 읽어보면 복잡해 보이지만, 그냥 bfs로 탐색할 경우에 깊이가 2인 노드의 수를 체크하면 된다. 문제 분류에 플로이드-와샬 이라는 태그가 있는데, 사실 이거 뭔지 모르겠다. 몰라도 풀리긴 하는데, 나중에 한번 살펴봐야 할 듯 하다. 문제 풀이 구상을 간단히 해보자. ..

문제를 살펴보고 오자. www.acmicpc.net/problem/1325 > N >> M; while (M--) { cin >> a >> b; v[b].push_back(a); } ans = 0; for (int i = 1; i

'치즈' 라는 이름을 가진 문제가 2개 있다. 두 문제는 다른 문제이다. 링크에 들어가서 2638 '치즈' 문제의 설명을 보고 오자. www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 기존의 2636 '치즈' 의 문제랑 상당히 유사하다. 하지만 다른 점이 있다면, 치즈의 2면 이상이 공기랑 접촉해 있을 때, 치즈가 사라진다는 조건이다. 치즈가 2면 이상 공기랑 접촉해 있는 것을 어떻게 알 수 있을까? 답은 2번 방문했을 경우를 예외로 두면 된다. 2번..

링크를 들어가서 문제의 설명을 읽어보고 오자. www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 이 문제는 bfs를 적절히 활용하면 쉽게 풀리는 문제이다. 공기라고 판단되는 칸 부터 bfs를 실행하여, 한 면이라도 치즈에 닿으면 없애버리면 된다. 이러한 과정을 반복하면서, 치즈가 사라질 때 까지 반복하면 간단히 풀리는 문제이다. bfs 탐색의 시작점은 (0,0) 으로 정했다. 항상 (0,0)은 공기이기 때문이다. 이 코드에서는 loc라는 구조체를 선언하여 좌표의 정보를..