https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 백트래킹 문제인데, 실수가 잦아서 헤맸다. 격자가 나오길래 처음엔 BFS인가 했지만 다 읽어보니 격자는 뭐 사용도 안 한다. 치킨집(chickens)과 집(houses) 배열에 각각 좌표를 넣고 (tuple) chickens의 조합을 구하면 된다. 여기서 실수한 게 바로, 순열을 구했다는 것..!! 시간초과 발생... [1,2,4] = [2,4,1] = [4,1,2] = ....

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 문제를 읽었을 땐 어떻게 하는 거야.. 흑흑 이랬는데 정작 풀어보니까 쉬운 문제였다... 백트래킹으로 생각하면 쉬웠는데 (DFS나 백트래킹이나..) 숫자를 그대로 두고 +로 할거냐 -로 할 거냐를 선택하면서 진행하면 된다. DFS로 지금까지 계산한 값에 numbers의 수를 더할지(0) 뺄지(1)를 넘겨주면 된다. target과 결과가 동일하면 ans++ 이런 형태의 코드를 볼때마다 내가 혼..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 사이클이 있는 것을 찾으면 된다. DFS를 통해서 시작 원소와 다음 원소를 인자로 두고 진행한다. 다음 원소를 가지고 쭉 DFS를 들어가다가 만약 다음 원소를 방문했고 시작 원소랑 다음 원소가 동일하다면 = 사이클 완성 > ans 벡터에 넣어주고 끝낸다. 만약 다음 원소를 방문했는데 시작원소랑 같지 않다면 = 사이클 안됨 > 바로 끝낸다. DFS를 나오면 이제 지금까지 지나온 사이클 ..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net A-B-C-D-E 이렇게 친구가 되면 친구관계가 존재하는 것인데, 즉 그래프 속 시작점에서부터 쭉 4개의 정점이 있으면 된다. 깊이 우선 탐색인 DFS를 사용하면 된다. 만약 A에 연결된 것이 B, C라면 B로 먼저 들어가서 쭉 갔다가 C에 들어가서 쭉 가려면 DFS 내에서 B로 갔던 것(visit)을 취소해야 한다. 그래야 C로 가는 길에 B를 만나도 중복처리를 하지 않기 때문이다. 그러므로 꼭 visit [x] = false를 해줘야 한다. 그리고 시작점이 0~n-1 모두 해당되기 때문에 꼭 vis..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음에 BFS로 풀다가 답이 제대로 안 나와서 뭐지? 했는데 다시 문제를 읽어보니.. DFS로 풀었어야 했다! 근데 당연함. 한 루트로 쭉 가는 거니까... 멍청하게 시간만 버림.. BFS로ㅋ 내가 넘 좋아하는 BFS 날 배신하다니... 근데 DFS로 막연하게 풀면 안 풀린다. 왜냐면 알파벳 방문 체크를 이미 해줬기 때문에 한 루트만 가고 끝이 나기 때문..!! 여러 루트를 모두 둘러보고 ..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 나올 수 있는 모든 수열을 만들어서 나중에 이게 나쁜 수열인지 좋은 수열인지 체크하는 건 시간 초과가 발생한다. 그래서 아무리 생각해도 어떻게 하면 좋을지 모르겠어서 다른 사람들의 코드를 확인했다. 이 분들은 수열을 모두 만들어서 하는게 아니라 하나씩(1,2,3) 붙여나가면서 그때마다 나쁜 수열인지 체크를 했다. 나쁜 수열이면 바로 끝내고 아니면 DFS를 통해서 계속해서 문자를 붙이도록 했다. 그래서 안 되는..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 노드 하나를 지울 것이다. 남은 트리에서 리프 노드의 개수를 구하자. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 루트 노드를 구하고 (m==-1 라면 root node) DFS를 root부터 시작해준다. DFS를 사용하면 서브 노드 끝까지 내려가게 되는데, child를 0으로 초기화하고 해당 노드의 서브 트리를 돌고, 만약 자식 노드가 하나도 없다면 1을 리턴하도록 한다..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 가장 헷갈리는 게 BFS, DFS 어떤 걸로 할지 결정하는 것 같다.. 뭔가 BFS 같은데 DFS인.. 근데 문제를 다시 보면 DFS로 해야 한다. 로봇청소기가 여러 곳으로 넓게 퍼지면서 이동하는 게 아니라 청소 안 한 곳만 바라보면서 계속 들어가기 때문에,, 처음에 BFS로 했다가 뭔가 안풀려서 DFS로 방향을 틀었다. 미리 알았다면 좋았을 텐데...^^ 문제를 읽어보면 조건들이 많은데, 이 ..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 각 지점들을 노드로 생각하고 DFS 혹은 BFS로 탐색하려고 한다. 이동하면서 맥주 20병을 모두 마시면 어떤 지점도 가지 못하게 되는데, 이를 제외하기 위해서 각 지점들의 거리가 1000보다 크다면 탐색하지 않도록 한다. (50미터당 한 병씩 이므로 최대 1000미터 이동 가능) 탐색 가능한 지점들만 graph라는 벡터에 넣어서 서로 연결해준다. #include #include #inclu..