전체 글102 [C] 9663: N-Queen 구현은 다음과 같이 진행했다. 1. 퀸이 놓이면 퀸이 공격할 수 있는 자리들에 chess배열에 1을 추가하여(색칠하여) 저장하였다. 1-1.이때 가로 세로는 그냥 칠하고 (겹치는거 빼줌), 대각선을 색칠할 때는 while문을 이용하여 색칠해줬다. 이때 색칠하는 방법은 전에 풀었던 "토마토"문제와 같이 미리 x,y좌표로 갈 수 있는 경우의 수를 배열로 저장하고 (x,y_coordinate) for문을 이용해 구현했다. 1-2 이때 그래프의 범위를 벗어나면 for문을 빠져나오도록 했다 2. 이후 빈 공간에 queen을 배치할 수 있는지 판단하고 배치 가능하면 color함수를 재귀적으로 호출한다. 2-1. 이때 계속 덧칠하면서 color을 호출했기 때문에 호출 후 return하면 다시 지워주기 위한 remov.. 2023. 8. 6. [C] 11724: 연결 요소의 개수 일단 이 문제도 결국 그래프 탐색 문제이다. 최단 거리와 관계가 없고 그냥 그래프가 서로 이어져 있냐만 확인하면 되므로 Depth-first(깊이 우선탐색)을 이용하여 인접행렬을 통해 문제를 풀었다. 여기서 유일하게 주의해야 할점은 노드가 하나라도 독립적인 연결 요소가 된다는 것이다. 그렇기 때문에 인접행렬에서 자기자신에게 가는 간선도 추가해줘야 간단히 풀 수 있다. #include int graph[1001][1001]; int visit[1001][1001]; void dfs(int n, int line, int x, int y) { for(int i=1;i 2023. 8. 6. [C] N과 M 백트래킹(Backtracking): 해를 찾는 도중에 지금의 경로가 해가 되지 않을 경우 그 경로를 더이상 가지 않고 되돌아오는 것! -> 모든 가능한 경우의 수 중 특정 조건을 만족시키는지 확인 -> 특정 조건 만족안하면 탐색 X -> DFS등에서 모든 경우의 수를 탐색하는 과정에서 같이 사용하여 더 이상 아니면 그 이전으로 돌아가서 다시 탐색 -> 조합과 관련된 문제는 백트레킹! -> 자기 자신을 호출하는 재귀함수를 주로 이용, 탈출 조건 잘 써야함! 15650 N과 M(2) -> 중복 안됨 -> 오름차순 #include int arr[11]; void ascend(int front,int n, int m, int cnt) { for(int i=front;i 2023. 8. 5. [C] 7569: 토마토 7576 토마토 문제와 거의 유사하지만 전에 문제는 2차원 배열, 이번 문제는 3차원 배열로 풀어야한다는 점에서 다르다. 전에 코드에 비해 나아진 점을 찾아보자면! 1. graph 값을 저장하면서 동시에 익은 토마토가 있는 경우에 바로 queue에 저장해뒀고 2. 몇번째 날에 익었는지를 새로운 배열로 선언하지 않고 queue 배열을 [][4]로 지정하여 0에는 z, 1에서 y, 2에는 x, 3에는 익은 날짜를 저장함으로써 가독성을 높였다. 3. 익은 토마토 개수와 토마토가 없는 자리의 개수를 따로 구함으로써 예외인 경우를 처리해줬다. 주의해야할 점을 찾아보자면! 3차원 문제이기때문에 Z,Y,X 순서를 헷갈리지 않아야하고 맨 마지막에 bfs()함수에서 return 할때 queue[rear][3]에는 아무런.. 2023. 8. 4. 이전 1 ··· 12 13 14 15 16 17 18 ··· 26 다음