백준
[백준] 17070번 - 파이프 옮기기 1
💡 깊이 우선 탐색 (DFS) 삼성 A형 기출문제라 해서 풀어봤는데, DFS로 손쉽게 풀 수 있는 알고리즘 문제였다. 먼저 파이프를 밀어 옮겨야하는 상황에서 파이프에 옮기는 방법은 가로 2가지, 세로 2가지, 대각선 3가지인데 DFS를 이용해 조건을 잘 맞추어 모든 상황을 고려해 만들어주면 된다. 가로인 경우 - (x,y+1), (x+1,y+1) 세로인 경우 - (x+1,y), (x+1,y+1) 대각선인 경우 - (x,y+1), (x+1,y), (x+1,y+1) 이때 주의할점은 옮겨야 할 곳이 1인 곳은 가지 못하도록 해줘야하는데 가로와 세로는 각각 (x+1, y)와 (x, y+1)만 고려해주면 되지만 대각선은 (x-1,y) (x,y-1) (x,y), 총 3가지를 고려해줘야 한다. ✏️ 구현 코드 #in..
[백준] 11657번 - 타임머신 (벨만-포드 알고리즘)
☞ 이 문제에서는 음수 간선이 존재하며, 출력 내용에서의 "만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다." 를 보면 그래프에 음수 사이클이 존재하는 경우 -1을 출력하라는 말이라고 볼 수 있다. 따라서 음수간선이 존재하며 음수 사이클의 존재를 판단 할 수 있는 '벨만-포드 알고리즘'을 사용하면 된다. '벨만-포드 알고리즘'은 아래에 잘 설명이 되어있으니 참고해주세요. https://withseungryu.tistory.com/34 벨만-포드 알고리즘 (Bellman-Ford Algorithm) ☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로..
[백준] 2014번 - 소수의 곱
☞ 이 문제에서 가장 중요하게 생각 할 점은 배열에 저장되어 있는 소수들을 어떤 방식으로 곱해야 최대한 순서대로 저장시킬 수 있도록 해줘야 합니다. 그냥 순서대로 처음에 한개씩 다음에 2,2 2,3 2,4 2,5와 같이 2개씩 계산을 해서 우선순위 큐에 저장시켜주면 나중에는 같은 수로 곱하여도 차이가 많이 나기 때문입니다.(예를 들어 2*2*2 와 7*7*7의 차이가 어마어마하다.) 따라서 여기서 우선순위 큐를 이용해 앞에 있는 수와 배열에 저장되어 있는 수들을 곱해 우선순위 큐에 저장시킨 후 다시 앞에 있는 수와 배열에 저장되어 있는 수들을 곱하는 방법을 반복한 후 N-1번째까지 반복 한 후 맨 앞에 있는 수가 정답이라는 것을 알 수 있었습니다. 여기서 2*2 를 하고 2*3 2*5를 가는 것보다 맨 ..
[백준] 6593번 - 상범 빌딩
이번 상범 빌딩 문제는 행렬에서 너비우선탐색(BFS)을 이용해 시작점에서 각 위치의 거리만 구할 수 있으면 쉽게 풀 수 있다. 다만, 3차원 행렬을 사용해야하기 때문에 중간 중간 헷갈렸다. queue를 만들때 x,y,z를 다 저장하고 싶은데 지금까지 2개만 묶어서 저장했던 pair 방식 뿐이여서 인터넷에 3개를 묶는 방법을 찾아보며 시간이 소비했지만, 다행히 pair를 한 번 더 사용 할 수 있는 방법을 생각 할 수 있었다. #include #include #include #include #include using namespace std; int L, R, C; vector adj; vector dist; int dir[6][3] = { {1,0,0},{-1,0,0} ,{0,1,0} ,{0,-1,0} ..
[백준] 5014번 - 스타트링크
☞ 이번 문제는 풀면서 정말 많은 방법들을 갖고 접근해보았다. 처음에는 재귀를 이용해 풀려고 했는데, 재귀를 끝내기 위한 조건을 찾는 와중에 어떻게 하면 Up and Down을 계속 지속하며 뺑뺑 도는 부분은 나올 수 있을지에 대한 부분에서 막혔었다. 그래서 다른 방법을 찾아 보았고, 대부분 어떤 점에서 다른 점까지의 거리를 구하는 문제에 사용되는 너비우선탐색(BFS)법을 사용해보았다. ● BFS로 풀기 위해 해당 건물을 인접리스트의 형태로 표현 해보았다. int tmp[2] = { U, -(D) }; for (int i = 1; i > F >> S >> G >> U >> D; adj = vector(F+1); int tmp[2] = { U, -(D) }; for (int i = 1; i
[백준] 2178번 - 미로 탐색
이 문제는 위의 그림과 같이 입구(0,0)에서 출구(N-1,M-1) 까지의 거리를 찾는 문제이다. 거리를 찾는 문제이기 때문에 너비우선탐색을 이용해서 푸는 방법을 쉽게 생각 할 수 있었다. matrix를 이용해서 문제를 풀면 간다하며 마지막으로 저장되어진 dist 행렬에서 N-1,M-1번째 수만 결과를 출력하면 간단하게 풀 수 있다. 여기서 더욱 더 시간을 줄이기 위해 방향을 아래와 같이 행렬에 저장하였다. int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} }; #include #include #include #include #include using namespace std; int N, M; int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} }..