bfs
-
2117.홈 방범 서비스알고리즘/SW Expert Academy 2020. 6. 6. 21:30
이번에 풀어볼 문제는 SW Expert 2117 홈 방범 서비스다. 난이도는 역시나 그렇게 어려운 거같진 않지만 이번에 느낀점은 역시 예외상황을 확인하려면 예시를 잘봐야한다. 이 문제에서 나의 실수는 탐색에 있었다. 이 문제는 전부다 탐색을 해봐야 하는데.. 나는 집위주로만 탐색을 했다. 허허허.. 여튼 다시수정했으니 됐지만... SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 탐색을 언제 끝마칠지 판단해야함 => 서비스 범위가 맵을 넘어서면 정지 2. 언제 최대값을 가져갈지 생각해야함 => 이득 - 운영비용이 적자가 나지 않으면 해당 값을 최대치와 비교 3. 탐색하는 좌표에 집이 있는 경우 => 집 갯수..
-
1949.등산로 조성알고리즘/SW Expert Academy 2020. 6. 3. 22:51
이번에 풀어볼 문제는 SW Expert의 1949 등산로 조성이다. ( 아래링크는 SW Expert 로그인하고 눌러야함.. ) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 난이도는 높지않지만 한 가지를 빼먹어서 테스트 케이스 50개중 48개만 맞았다.. 제엔자앙!!!!!!! => 완벽한 설계인줄 알았는데... 닿을 듯 말 듯하네.. ㅎㅎ 여기서 중요한 점은 깎는 점에 대한 처리인데 언제깎아야할지는 생각보다 간단하다. 0. 제일 높은 봉우리를 찾고난 뒤 => 제일 높은 봉우리 일때만 해당좌표를 시작으로 탐색을 진행한다. => 탐색(BFS)은 재귀함수로 진행!! => 그렇지 않으면 c..
-
1697.숨바꼭질알고리즘/백준 BAEK JOON 2020. 5. 27. 03:21
1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 이번에 풀어볼 문제는 백준의 1697 숨바꼭질이다. 어떻게 접근을 시작하는지, 설계를 시작하는지에 따라 체감하는 난이도는 크게 차이가 날 것 같다. 나같은 경우에는 금방 풀이법을 찾아냈다. 대부분이 금방 찾아내는 경우라면 쉬운편에 속하는 것이고 아닌 사람들 굉장히 헤맬 것이다. 결론을 말하자면 이번문제는 BFS로 간단하게 풀어낼 수 있는 문제이다. 주의할 점이 있다면 같은 연산을 줄이는 것이다. 이것만 주의하면 충분히 풀 수 있는 문제..
-
2468.안전영역알고리즘/백준 BAEK JOON 2020. 5. 26. 23:01
이번에 풀어볼 문제는 백준의 2468 안전영역이다. BFS, DFS(재귀,스택,큐)로 풀이가 가능하다. 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 나는 BFS를 이용해서 풀이를 진행하였고 난이도는 역시 그렇게 어려운 편은 아니다!! 모든 문제가 그렇지만 설계단계를 잘생각해서 진입해야 헤매지 않고 풀이에 성공할 수 있다. 이 문제는 직전에 포스팅 한 문제들과 다를 바없이 탐색이 문제를 푸는관건이 아니라 탐색 이전까지의 로직을 구현해내는 것이 관건인 문제이다. 이 문제에서는 물에 잠기는 최소높이와 최고높이를 저..
-
7576.토마토알고리즘/백준 BAEK JOON 2020. 5. 25. 21:18
이번 문제는 토마토이다! 비교적 쉬운 문제에 속한다. BFS를 이용하면 간단히 풀 수 있는데 BFS로 퍼지면서(토마토가 익으면서) 내부의 값(걸리는 시간값)을 잘 지정해주어야한다! 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net #pragma warning(disable:4996) #include #include #define MAX 1001 using namespace std; int n, m; int map[MAX][MAX]; int dx[4] = { -1, 1, 0..
-
14502.연구소알고리즘/백준 BAEK JOON 2020. 5. 25. 07:09
이번 문제는 연구소이다. 꽤 많이 중요한 내용을 배우고 상기할 수 있는 문제였다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 이 문제를 푸는데 핵심은 맵을 복사해서 사용한다는 것과 나머지는 탐색이다. 난이도는 어려운 수준이 아닌 거 같지만 초보자에게 연습하기는 좋은 문제인 것 같다( 난 초보자 ㅠㅠ.. 너무좋네...) 재귀함수 관련된 문제를 조금 더 풀어봐야할 것 같다. * 문제풀면서 중요한점 1. 문자, 특수기호 실수 => 실수로 자꾸 if문 다음에 변수에 값을 대입할 때 "=" 대신 "=="를 사용하여 틀림 주의..
-
2667.단지번호붙이기알고리즘/백준 BAEK JOON 2020. 5. 21. 23:40
이번에 풀어볼 문제는 단지번호붙이기이다. 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 생각보다 이상한곳에 막혀서 시간낭비를 했다. 시간은 1시간 30분정도 걸렸고 목표한 시간보다 30분이나 초과되었다. 사실 30분컷 낼 수 있었는데 이걸 코드하나를 잘못집어넣어서 하루종일 걸렸다.. 후... DFS를 이용해서 풀었고 이 문제의 포인트는 Stack를 이용하되 Stack에 자신이 이동한 부분의 좌표를 넣어주는 것이다. 그래야지 DFS로 쭈욱 탐색하다가 막혔을 때 다시 돌아가서 탐색하지 않은 방향으로 탐색을 진행..
-
1260. DFS와 BFS ( Stack & Queue 사용 )알고리즘/백준 BAEK JOON 2020. 3. 10. 01:25
이번에 풀어볼 문제는 백준 1260번 이며 완전탐색 알고리즘의 대표 DFS와 BFS이다. # 많은 블로그에서 해당 알고리즘에 대한 자세한 설명이 되어있으니 참고!! 나의 경우는 DFS의 경우 재귀함수를 사용해서 풀어도 되지만 굳이 Stack을 너무나 사용해서 풀고 싶었다. 알고리즘을 다시 시작한지 얼마안되서 꽤 오랜시간이 걸렸지만 그래도 해내서 다행이다:) Stack과 Queue에 대한 개념과 DFS와 BFS의 탐색 과정을 생각하며 구현하면된다! -> 구현을 외우는 것이 아니라 이해하는 것이 중요하고 예외처리를 잘 하는것이 가장 중요한 Point다! #include #include #include #define MAX 1001 using namespace std; int n, m, ..