Programming/BOJ (42) 썸네일형 리스트형 [백준/C++] 2644번: 촌수계산 코드는 간단하지만 나는 이해하는데 한참 걸린 것 같다. 1) 촌수는 결국 시작점에서 끝점으로 갈때까지 몇 개의 열을 거치느냐(depth)/거리가 있느냐를 따지는 문제와 같아진다. 2) map구성하기: 방향 역시 양방향 모두 같은 결론에 도달한다. 3->7을 가는 경로나 7->3을 가는 경로나 같은 결과를 낸다. 그러므로 map을 구성할 때 양방향 모두 똑같이 길을 만들어 주면 된다. 3) 또한 기존 2D map이 상하좌우로 이동할 수 있는 것과 달리 이 문제의 경우 한방향으로만 탐색을 진행해야 한다. 시작점이 7이기 때문에 7번째 행부터 탐색하기 시작한다. 처음엔 (7,2)에 방문한다(방문:2로 표시함). 주의할 점은 (2,7)에도 방문했다고 체크를 해줘야 된다.(둘이 같은 관계이므로) 그 다음엔 2번째.. [백준/C++] 6603번: 로또 1) 이건 test case 갯수를 입력으로 받지 않고 0이 나오면 끝나게 해야했다. 그 부분을 잘 몰랐는데 while문으로 구현하면 된다. 2) 조합을 만드는 문제는 탐색으로 풀면 된다. 1차원배열 탐색을 하면되고 dfs로 풀었다. 이전에 풀었던 알파벳문제와 유사했다. 3)종료조건: 6글자를 다 채웠을때 출력하고 return한다. 4)이 포스팅의 구현을 보고 따라했고 이전에 알파벳풀었을 때는 visit을 표시했던 것과 다르게 엄청 코드가 간단하다.... 하지만 어려워ㅠㅠㅠㅠ #include using namespace std; int num; int lotto[14]; int ans[6]; void dfs(int start, int depth) { //종료조건 if (depth == 6) { for (.. [백준/C++] 7562번: 나이트의 이동 이 문제는 보자마자 이동방향만 기존과 다르게 8방향을 설정하고 bfs를 돌리면 되겠다. 하고 감이 왔다. 하지만 너무 피곤해서 집중력이 안좋아 여러 오타가 발생했고.... 그래서 푸는데 오래 걸렸다. 1) index를 주의하자..... 변수이름이 여러개 나오니까 헷갈리지 말고 잘 써야한다. 나같은 경우 cx를 x, cy를 y라고 써놓고 계속 왜틀렸는지 모르고 있었다. 혹은 x와 y를 반대로 쓰지는 않았는지 복붙하다가 x만 두번 쓰지는 않았는지 주의해야함. 2) initialize를 해줘야 다음 test case에서 오류가 안난다. 3) map만 initialize했다가 또 오류가 났다. 이때가 젤 빡쳤는데 queue도 initialize해줘야한다. 전역변수로 설정했던 애를 bfs 블럭안으로 넣어서 bfs.. [백준/C++] 14503번: 로봇청소기 (DFS/구현) (**삼성 SW 기출문제) 조건들이 까다로워서 어려웠다... 내가 푼건 아니고 남이 푼거보면서 안보고 그대로 작성해봤다. 반시계방향으로 회전하면서 바라본다는 점을 생각해야하고 또 하나는 다 돌아본다음에 그 방향을 유지하고 후진해야한다는거.... 진짜 읽은 그대로 코딩해야된다. 너무어렵다.. 갈길이 멀구나 힘을내자. #include using namespace std; int n, m; int map[51][51]; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; int ans; void dfs(int cx, int cy, int cd) { if (map[cx][cy] == 0) { map[cx][cy] = 2; ans++; } for (int i = 0.. [백준/C++] 백준 10026번: 적록색약 기존에 풀었던 아파트단지에 숫자매기는거보다 더 쉬웠다. 흠... 어제 푼게 너무 어려워서 그런가... 주의점은 적록색약일 때, 그냥 같은 문자로 바꿔버리고 dfs를 진행하면 된다. 그리고 visit배열을 다시 초기화 해줘야한다. #include using namespace std; int N; string map[101]; int visit[101][101]; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; void dfs(int x, int y) { for (int i = 0; i = N || ny = N) contin.. [백준/C++] 백준 2667번: 단지번호붙이기 지금까지 엄청 쉬운 것만 풀다가 좀 막혔다... 1) 왠만하면 input을 받을 때 string배열로 받자. (문자가 붙어서 나오는 map) 2) 이렇게 여러개를 그룹지어야 하는 경우 dfs를 여러번 돌려야한다. 3) vector로 단지마다의 가구수를 count해서 넣으면 vector의 size가 곧 단지 수.. String으로 받을 때, #include #include #include using namespace std; //input int N; string map[26]; //output int cnt = 0; vector people; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, 1, -1 }; void dfs(int x, int y) { for (int i.. [백준/C++] 2606번: 바이러스 (플로이드 와샬/DFS/BFS) 플로이드 와샬 알고리즘을 공부했다. 이 방법은 모든 정점에서 모든 정점으로의 최단경로를 구하는 방법이라고 한다. 이 문제의 경우 연결되었냐 or 연결되지 않았느냐 판단하는 문제여서 경로를 구할 필요도 없고 모든 정점에 대해 판단하지 않고, 첫번째 컴퓨터를 기준으로 판단하기 때문에 굳이 플로이드 와샬을 쓸 필요가 없지만 쉬워서 이걸로 풀었다. 오늘은 dfs, bfs로도 풀어봐야지. 3중 for문을 다 돌았을 때, 연결되어있는 노드라면 inf 가중치를 갖지 않을 것이다 라고 하고 풀었다. 플로이드 와샬 풀이 #include #define inf 99999 using namespace std; int map[101][101]; int computer; int main() { int N; pair pair; c.. [백준/C++] 백준 2309번: 일곱 난쟁이 이중 for문 탈출에 유의해야한다. 9명 중 7명을 찾는 것은 반대로 2명을 찾아 없애는 것과 같다는 것을 이용해서 풀었다. 이중 for문은 flag를 이용해서 탈출했다. #include #include using namespace std; int a[9]; int main() { int sum = 0; for (int i = 0; i > a[i]; sum += a[i]; } int flag = 0; int charge = sum - 100; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (i == j)continue; if (a[i] + a[j] == charge) { a[i] = 9999; a[j] = 9.. 이전 1 2 3 4 5 6 다음
