본문 바로가기

ALGORITHM/DFS, BFS

 (11)
[Swift] Lv3. 여행경로 (dfs) https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 생각 경로를 찾아서 갔다가 아니라면 return 해주기 나라 전체 방문이 아니라 티켓을 모두 쓰는(방문하는) 문제였다. dfs를 오랜만에 봤더니.. 어떻게 푸는지 까먹어서 많이 헤맸다.. 코드 전역변수를 안쓰려고 하다보니 매개변수 넣는 부분이 너무 ~ 길어져서 조금 코드가 복잡해졌다. 1, 2번 테스트 케이스를 틀렸는데 아래 ..
[Swift] 2234 성곽 (BFS) https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 생각 [ struct wall ] wall은 벽에대한 정보보다는 그 위치의 대한 정보라서 - 위치 r, c - 동서남북 벽의 유무 - 방의 번호 : 벽을 허물었을 때 현재 방의 넓이를 알 수 있도록 로 선언하였다. c++ 로 풀 때는 Bool { switch direction { case 0: return west case 1: return north case 2: return east ca..
[Java] 17406 배열 돌리기 4 17406 배열 돌리기 4 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 구현 + DFS (순열) 돌리는 경우의 수를 DFS로 구현해서 완성되면 배열 돌려기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.io.FileInputStream;..
[c++] 타겟 넘버 (프로그래머스 - dfs) https://programmers.co.kr/learn/courses/30/lessons/43165# 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr pass by reference로 answer 변수를 넘겨줘서 해결했는데 int dfs 로 return 1 했을 땐 결과가 나오지 않아서 슬퍼하는중 #include #include using namespace std; void dfs(vector &numbers, int order, int maxOrder,..
2580 스도쿠 백트래킹 문제 처음에는 가로, 세로 , 3x3 네모칸 안에서 없는 숫자를 찾아서 넣으려고 했더니 런타임 에러가 떠서.. 1부터 9까지 넣어놓고 안되면 지우는 방식으로 고쳤다. 지금 생각해보니 없는 숫자를 배열로해서 찾고 포문을 돌리면 될거같은데.. 더 시간이 걸리려나 (isRowOK 를 두번써서 하루종일 왜틀렸는지 찾고있엇다ㅜㅜㅜ) #include #include #include using namespace std; typedef pair pii; int sudoku[9][9], zeroCount; vector zero; bool IsRowOK(int x, int num) { for (int i=0; i
14889 스타트와 링크 시간 초과가 왜 나지 고민하다가 팀원 능력치 더하는 부분을 바꿔봤는데도 시간 초과 아예 재귀 부분 for문에서 시간 초과가 나는듯해서 for문의 시작 지점을 현재 멤버로 교체해서 통과 굳이 똑같은 부분을 반복하고 있었다.. #include #include using namespace std; int N, S[21][21], team[21], minStats = 1000000, teamStats1, teamStats2; void subStats() { teamStats1 = 0; teamStats2 = 0; for (int i=0; i j) { S[j][i] += S[i][j]; } } } backtracking(0, 0); cout
9663 N-Queen 이전에 풀었을 때 코드를 보니 이차원배열을 다 확인해서 시간이 일차원배열로 풀었을 때보다 두배나 더들었다. 전체 코드 #include using namespace std; int N, cnt; int board[15]; bool isSetQueen(int row) { for (int i=0; i N; setQueen(0); cout n; cout
15649 N과 M (1) 백트래킹 기본기본문제 #include #include using namespace std; int N, M; int arr[9]; bool visit[9]; void backtracking(int cnt) { if (cnt == M) { for (int i=0; i

티스토리툴바