궤도

문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제랑 똑같은 유형인데 그냥 방향이 4개에서 8개가 됐을 뿐이다. 소스코드 #include #include #include #include using namespace std; int matrix[300][300], l; pair dir[8] = {{1, -2}, //나이트가 갈 수 있는 방향 {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -..

문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신이 없다. 먼저 난 처음에 기존에 미로찾기 처럼 input 배열을 갱신하는데 이제 벽을 부쉈는지 아닌지를 기록하면 될 것이라고 생각했다. 하지만 이 문제는 2차원 배열 하나로 간단하게 풀리는 문제가 아니었다. 이런 배열이 있다고 하자. 당시엔 matrix를 갱신할 생각이었어서 벽을 -1로 표현했다. 아직 벽을 부술 수 있는 상태는 파란색, 벽을 더이상 부실 수 없는 상태는 빨간색으로 표현했다. 좀 더 진행했다. 보라색은 벽을 부수고도, 안부수고도 갈 수 있음을 나타냈다. 아무튼 이렇게 벽을 부순 상태에서 갱신된 3,..

문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아직 방문한 적 없는 좌표라면 X까지 오는데 걸린 시간에 1을 더해 갱신하면 된다. myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제에서 상하좌우만 뺀거라고 생각해도 된다. 소스코드 #include #include using namespace std; ..

문제 풀이 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줄씩 더 생긴다고 큰 일이 일어나진 않을테니까... 소스코드..