Machineboy空
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제요약 상하좌우로 이동하는 불, 지훈이는 미로에서 탈출가능한 지 난이도 Gold 4 풀이 포인트 BFS REVIEW 우선, 불이 여러 군데서 발생할 수 있다는 것과 발생하지 않을 수 있다는 것을 간과했다. 문제를 제대로 읽자. 그리고 아직 bfs와 dfs의 용도를 완벽하게 파악하지 못했나보다. 불은 dfs로 퍼져나가고, 지훈이는 bfs로 최단 거리 내에 이동해야한다고 생각했다...
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제요약 조건에 따라 인구 이동이 일어나는 횟수 난이도 Gold 4 풀이 포인트 DFS, connected componet 문제임을 파악하기 REVIEW 우선, 2차원 좌표를 1차원으로 묶어서 생각하는 법을 생각하다가 어후 너무 복잡해져서 풀이를 관두었다.. 정말 간단하게 생각하면 된다. 기존 DFS을 돌릴 때 육지라면 ( a[ny][nx] ==1 ) 이면 이동했던 것을 문제의 조..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제요약 최단거리가 가장 먼 육지의 두 곳에 보물심기 난이도 Gold 5 풀이 포인트 BFS를 실행하면, 한 칸씩 움직일 때마다 최단거리가 갱신됨 즉, 도착 지점 과 출발지점 쌍이 계속 나오기 때문에 2쌍을 뽑아서 돌릴 필요가 없다. BFS void bfs(int y, int x) { memset(visited, 0, sizeof(visited)); visited[y][x] = 1; queue q;..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제요약 트리 구조에서 한 노드를 지웠을 때 리프노드의 개수를 구하라. 난이도 Gold 5 //내 코드 #include using namespace std; int n, a[52], k, ret; vector adj[52]; bool b[52]; void cut(int node) { b[node] = false; for (int s : adj[node]) { cut(s); } } int ma..