BFS (6) 썸네일형 리스트형 [ 백준 2573 ] 빙산 (C++) BFS 풀이 # 문제링크 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS 돌리면서 0 만나면 map에 -1 씩 해주고, 0이 아니면 queue 에 넣어서 계속 돌려주면 된다. 그렇게 한 덩이가 2개 이상이면 return 해주면 된다! # 제출 코드 #include #include #include using namespace std; int N, M; int map[300][300]; void input() { scanf("%d %d", &N, &M); for.. [백준 9205] 맥주 마시면서 걸어가기 (C++) DFS, BFS 풀이 # 문제링크 www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 이걸 첨에는 현재 좌표부터 1000m 거리 이내에 있으면 다 해보면 된다고 생각해서 DFS로 짰는데 시간초과가 났다. 사실 편의점의 갯수 n 이 100이니까 그냥 100개의 노드에서 DFS를 돌리면 시간초과는 당연한 결과다. 좌표값들을 정렬한다음에 우선순위로 하면 되지 않을까? 이런 생각도 했었는데, 잘못된 방법이었다. 결론 먼저 말하면, BFS로 풀거나, DFS로 풀때는 이미 방문한 노드를 .. [백준 14502] 연구소 C++ # 문제링크 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 비슷한 문제를 풀어봐서 금방 풀었다. map 크기는 8 * 8 이 최대고, 세울 수 있는 벽은 세 개이다. 맵이나 depth가 이렇게 작으면 노가다로 풀어도 된다. 1) map 에서 0인 좌표 중에 벽을 세울 위치 세 군데를 DFS로 고른다. (chk배열에 true로 체크) 2) 해당 위치에 벽을 세워주고 바이러스 위치부터 BFS를 돌린다. map에 직접 바이러스(2) 표시를 한다. 3) 이후 안전한 공간의 개.. [백준 2146] 다리 만들기 # 문제링크 www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net DFS를 사용하여 섬을 구분하고, BFS를 사용해서 가장 짧은 거리를 찾는 문제. DFS, BFS 둘 다 써야하는 문제였어요. 문제 예시로 준 섬입니다. 이를 아래처럼 0과 1로 표시할 수 있습니다. 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.. [백준 7576] 토마토 # 문제 링크 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 쉽게 생각했다가 엄청 고생한 문제다. 1로 표시된 익은 토마토부터 최단거리 구하는거니까 BFS 로 구하면 되겠네~ 했다. 그래서 배열을 입력 받은 후 for 문 돌려가며 1을 찾아서 DFS를 돌렸고, 가장 작은 수로 배열을 채웠다. 테스트 케이스를 돌렸을 때는 다 맞았는데, 제출을 하면 계속 틀렸다고 나왔다. 뭐가 틀린지도 모르고 계속 싸매다가 결국 구글링을 했다. 바로 속이 싸악.. [백준 1260] DFS와 BFS # 문제 링크 www.acmicpc.net/problem/1260 # 제출 코드 #include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; void dfs(int node) { check[node] = true; cout start; for(int i =0; i> u >> v ; a[u].push_back(v); a[v].push_back(u); } for(int i = 1; i 이전 1 다음
