궤도

문제 풀이 myunji.tistory.com/285 [백준] 7576번 : 토마토 문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파 myunji.tistory.com 이 문제의 3차원 버전이다. 풀이는 완전히 똑같으니 그건 어렵지 않았고, 3차원 배열 문제를 풀일이 많이 없어서 입력이 제일 어려웠다. 소스코드 #include #include #include #include #include using namespace std; struct pos { int x, y, z; }; //범위 초과 때문에 상하좌우 한줄씩 추가 int matr..

문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제랑 풀이가 거의 똑같다. 다만 모든 토마토를 방문하지 못할 수도 있는 경우를 체크해줘야 한다는 것과 가장 마지막에 익을 토마토(도착점)이 무엇인지 모른다는 것만 다르다. 소스코드 #include #include #include #include #include using namespace std; //범위 초과 때문에 상하좌우 한줄씩 추가 int matrix[1002][1002]; int N, M..

문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바로 아래, 오른쪽에 있는 좌표까지의 최단거리는 2일 것이다. 그 다음엔 이렇게 되고, 계속 하다보면... 이렇게 최단거리를 찾았다. 지금 이 과정은 bfs로 한거나 다름없다. 왜냐하면 시작점(1, 1)에 대해 갈 수 있는 좌표((2, 1), (1, 2))를 큐에 넣었고 최단거리가 2인 좌표들을 순서대로 방문하며 갈 수 있는 좌표((3, 1), (2, 2), (1, 3))를 큐에 넣어 또다시 순서대로 해당 좌표들을 방문하며 진행했기 때문이다. 그럼 왜 dfs는 안될까? 그림을 통한 설명을 하기 전 간단하게 말하자면 dfs는..

문제 풀이 myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 myunji.tistory.com 이 문제와 풀이가 동일하다. 오히려 이 문제는 연결된 배추의 그룹(?)수만 세면 되는거라 더 쉬운 셈이다. 소스코드 #include #include #include using namespace std; //범위 초과 때문에 상하좌우 한줄씩 추가 int matrix[52][52], M, N; pair dir[4] = {{-1, 0}, //상 {1, 0}, //하 {0, -1}..

문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 건 더이상 해당 root와 이어진 1이 없다는 뜻이니까 다시 새로운 1이 나올때까지 배열을 돌면 되겠다. 난 그냥 편하게 재귀함수 돌리려고 dfs로 했다. 그나저나 이런 문제를 풀땐 상하좌우로 이동하면서 풀어야 하는데.. 아무생각없이 상하좌우로 이동하다간 5x5배열에서 [-1][0]을 참조하거나 [6][2]를 참조하게 될 수도 있다. 이걸 해결하는 방법은 여러가지가 있지만 난 이렇게 상하좌우 테두리를 둘러주는 방법을 선호한다. 위아래 2줄씩 더 생긴다고 큰 일이 일어나진 않을테니까... 소스코드..

문제 풀이 DFS 또는 BFS로 정점 1과 연결된 정점의 수를 세면 된다. 난 그냥 편하게 DFS를 재귀함수로 구현했다. 소스코드 #include using namespace std; int matrix[101][101], cnt; bool visited[101] = {false}; //정점의 방문 여부 void dfs(int cur, int max) { //재귀함수로 구현 for (int i = 1; i > N >> M; for (int i = 0; i > first >> second; matrix[first][second] = 1; matrix[second][first] = 1; } visited[1] = true; dfs(1, N); cout

문제 풀이 그래프 탐색 방법에 속하는 DFS와 BFS를 구현하는 문제이다. DFS는 깊이 우선 탐색으로 보통 스택 또는 재귀로 구현한다. BFS는 너비 우선 탐색으로 보통 큐로 구현한다. BFS와 DFS의 그래프 순회 순서를 나타낸 그림이다. 대충 BFS는 왼쪽->오른쪽, DFS는 위->아래로 생각하면 된다. 소스코드 #include #include #include #include using namespace std; int matrix[1001][1001]; //정점 i와 j 사이에 간선이 존재하면 matrix[i][j]=1 bool visited[1001] = {false}; //정점의 방문 여부 void dfs(int start, int max) { //스택으로 구현, 재귀로 구현해도 됨 stack..

문제 풀이 이 문제의 시간 제한은 0.1초다. 그니까 입력이 들어오자마자 바로바로 출력을 내보내야 한다는 것이다. 입력을 받을 때를 제외하곤 단 하나의 for문도 쓸 수 없다. 그럼 도대체 제일 작은 값도 제일 큰 값도 아닌 중앙값을 바로바로 내보낼 것인가... 중앙값을 기준으로 그보다 작은 수는 최대 힙에 넣고 그보다 큰 수는 최소 힙에 넣는 것이다. 그렇다면 최대 힙의 top에는 중앙값보다 같거나 작은 수 중 가장 큰 수가, 최소 힙의 top에는 중앙값보다 같거나 큰 수 중 가장 작은 수가 올 것이다. 균형을 이루기 위해선 최대 힙과 최소 합의 원소의 갯수 차이가 0(원소의 총 갯수가 홀수)이거나 1(원소의 총 갯수가 짝수)이여야 한다. 만약 이 균형이 깨진다면 중앙값을 수정해야 한다. 위 상태에서 ..