BFS
-
SWEA 2117 : [모의 SW 역량테스트] 홈 방범 서비스백준 문제풀이/GRAPH 2020. 6. 7. 00:03
문제 문제 풀어보기 풀이 테스트 케이스를 통과하기 위해 문제 꼼꼼히 읽자!!! 내일 삼성 코테보러갑니다. ㅈㅅ 주의할 점 1. 집이 1개 일수도 있다. 2. 최대 20 x 20 까지의 거리를 보자 3. 거리마다 bfs 하지 말고 한 번에 하고 계산하자. 코드 #include #include #include #include #include #include using namespace std; #define safe(x,y) x>=n || x maxSz) maxSz = dist[nx][ny]; q.push({ nx,ny }); } } // 각 거리마다 수익계산 int cnt = 0; for (int k = 1; k T; for (int i = 1; i < 50; i++) { pay[i] = (i * i) +..
-
SWEA 1953 : [모의 SW 역량테스트] 탈주범 검거백준 문제풀이/GRAPH 2020. 5. 29. 19:27
문제 문제 풀어보기 풀이 비트 마스크를 통해 길이 이어져있는지만 확인하면서 BFS를 하면 풀 수 있는 간단한 문제입니다. 그 간단한 문제를 저는 엄청 실수를 많이 했네요. 비트 마스크 할 때 항상 하는 실수인데 이진수랑 십진수를 자꾸 바꿔 쓰는 게 문제네요... 여러분들은 꼭 이진수 1000을 십진수 8이라고 쓰시기 바랍니다. 코드 #include #include #include #include using namespace std; #define safe(x,y) x>=n || x= 1) continue; int reverse; if (k % 2 == 0) reverse = k + 1; else reverse = k - 1; if ((arr[x][y] & (8 >> k)) && (arr[nx][ny] &..
-
BOJ 17142 : 연구소 3백준 문제풀이/GRAPH 2020. 5. 10. 21:39
문제 문제 풀어보기 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 간단하게 설명하면 모든 경우에 대해서 BFS를 전부 돌려봐야 하는 문제입니다. 어떤 바이러스를 활성화할 것인지를 고르는 방법이 포인트인데, 조합을 써도 되고 방법은 여러가지 입니다. 저는 비트 마스크를 사용해서 풀었으니 참고하시면 좋을 것 같습니다. 코드 #include #include #include #include #include #include using namespace std; int dx[] = { 1,-1,0,0 }; int dy[] ..
-
BOJ 12906 : 새로운 하노이 탑백준 문제풀이/GRAPH 2020. 3. 6. 14:22
풀이 문제 풀어보기 BFS 유형 중에서 이런 STL 을 사용하는 경우가 별로 없어서 포스팅해봤습니다. 이 문제에선 Array, String, Map 함수들이 사용됩니다. 우선 map 을 보겠습니다. map '변수명' 의 방식으로 사용되며 조금 어려울 수도 있는 함수입니다. 보통 bfs 에서 check[][] 라는 배열을 통해서 방문했던 위치를 파악합니다. 하지만 그게 좌표처럼 간단한 값이 아닌 경우 지금처럼 'aabbc' 라는 문자를 탐색했었는지?? 를 파악해야 하는 경우 map 함수가 사용됩니다. 그리고 이 문제에서는 그러한 key 값으로 array 이라는 배열을 사용했네요. 굳이 array 를 사용한 이유는 자료형과 크기를 확정 지을 수 있기 때문입니다. vector 의 경우..
-
BOJ 5213 : 과외맨백준 문제풀이/GRAPH 2020. 2. 19. 17:22
문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단 언어가 통하지 않기 때문에, 과외맨은 자신의 특기를 살려서 일주일간 과테말라에서 스페인어를 과외 받았다. (이하생략) 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가..
-
BOJ 1525 : 퍼즐백준 문제풀이/GRAPH 2020. 1. 24. 01:16
문제 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 1 2 3 4 5 6 7 8 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자. 1 3 4 2 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 6 7 8 가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오. 입력 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개..
-
[BFS] BOJ 2178 : 미로 탐색백준 문제풀이/GRAPH 2019. 8. 16. 00:30
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요. DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 예제 : 2019/07/22 - [프로그래밍/1일1백준] - [Graph] BOJ 1260 : DFS 와 BFS 문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할..
-
[BFS] BOJ 4963 : 섬의 개수백준 문제풀이/GRAPH 2019. 8. 15. 19:06
백준 알고리즘 강의를 토대로 작성된 문제풀이입니다. DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요. DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 예제 : 2019/07/22 - [프로그래밍/1일1백준] - [Graph] BOJ 1260 : DFS 와 BFS 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같..