backjoon
[백준] 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..
[백준] 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
[백준] 1780번 종이의 개수
3의 제곱만큼 늘어나는 종이에서 같은 숫자를 가진 3^n 의 종이의 개수 -1,0,1를 각각 찾는 문제이다. 처음에 브루트포스를 접근을 하려 했지만, 시간이 어마어마하게 나올 것 같아서 분할 정복을 도입해봤다. 다행히 문제에 3^N 으로 늘어나며, 종이를 자를때도 3^N이라는 규칙에 맞게 자르기 때문에 쉽게 규칙을 찾을 수 있었다. 우선 findPaper 함수를 만들어 NXN의 크기부터 검사를 하도록 하고, 같은 숫자로 다 이루어지지 않을 시에 (N/3)X(N/3)으로 N개만큼 분할해서 다시 구하도록 재귀 함수를 구현해주었다. firstx와 firsty를 이용해 규칙에 맞게 그 종이를 구성하는 첫번째 인자만 가져올 수 있도록 해주었다. 또한 구성된 숫자를 검사할때는 checkNum 함수를 이용해서 쉽게 ..
[백준] 1012번 유기농 배추
유기농 배추에 배추흰지렁이의 마리 수를 구하는 문제이다. 이 문제를 풀기위해서 완전탐색을 이용했는데, 먼저 ground 2차원 배열을 생성해서 배추의 위치를 1로 표현을 해주었다. 그 다음으로 groundN 함수를 사용해 groundN함수를 호출 했을 때 ground[x][y]의 위치가 1이면 배추가 있는 곳이므로 다시 탐색을 시도했을 때 탐색을 하지 않게 하기위해 1에서 0으로 바꿔주었다. 또한 이어져있는 배추를 확인하기 위해 [0,1] [1,0] [-1,0] [0,-1]. 동서남북으로 다시 탐색을 해줘, 그곳에도 배추가 있으면 또 탐색을 못하도록 1에서 0으로 값을 계속 바꾸어주었다. 이렇게 하면 나중에 ground배열에서 배추가 있는 위치를 찾을 때 또 다시 찾을 수 없도록 해줄 수 있기 때문이다...