목록dfs (6)

Written

백준 2206 <벽 부수고 이동하기> C++ 풀이

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한..
알고리즘 문제풀이 2023. 10. 12. 15:47
백준 16234 <인구 이동> C++ 풀이

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에..
알고리즘 문제풀이 2023. 10. 11. 12:39
프로그래머스 레벨2 <타겟 넘버> C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 어렵지 않은 DFS 문제였습니다. 주어진 vector의 현재 위치의 값을 더하는경우와 빼는경우를 체크해서 모든 경우를 탐색해보고 마지막 인덱스까지 갔을때, 그 값이 문제에서 주어진 타겟과 같으면 경우의 수를 하나 늘려주면 간단하게 답을 구할 수 있었습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..
알고리즘 문제풀이 2023. 9. 25. 21:00
프로그래머스 / 숫자 변환하기 / C++

처음엔 DFS로 완전탐색 방식으로 구현해봤는데, 테스트케이스 절반에서 시간초과가 나서 BFS로 바꾸었더니 시간초과 없이 전부 맞출 수 있었습니다. 문제를 풀 때, BFS를 사용할 수 있으면 BFS가 높은 점수를 받기에는 더 좋은 것 같습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #include #include #include #include using namespace std; // DFS로 완전탐색때는 시간초과 났었기때문에 B..
알고리즘 문제풀이 2023. 8. 29. 19:25
프로그래머스 / 무인도 여행 / C++

그래프 탐색 문제에서 보통 BFS를 많이 사용했었기 때문에 DFS로 풀어봤습니다. DFS에 지금까지의 날짜를 누적해가면서 넘기는 경우에는, 지도 형태에 따라 끊기는 경우가 있기 때문에, 이 부분은 조심해야 합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #include using namespace std; //d를 가지고 다니면 끊겼을때 제대로 더해지지 않으니 조심! int dx[4] = ..
알고리즘 문제풀이 2023. 8. 28. 20:26
백준 / 2606 / 바이러스 / C++ / 알고리즘 문제풀이

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제를 보고나서 드는 생각은 DFS로도 풀 수 있을것 같고, Union-Find로도 풀 수 있을 것 같다고 생각했는데 DFS로 문제를 풀어본지가 좀 오래된것 같아 DFS로 구현해서 풀어보았습니다. 컴퓨터간의 방향이 따로 없어서 인접리스트 형식으로 서로 연결되어 있게끔 데이터를 저장합니다. 그리고 문제가 1번 컴퓨터를 기준으로 시작하기 때문에 DFS(1)로 구현한 DFS함수를 호출합니다. DFS에 들어오..
알고리즘 문제풀이 2022. 11. 29. 21:02
이전 Prev 1 Next 다음