[백준 17129번/c++] 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유
문제 윌리암슨수액빨이딱따구리 식구의 위치에서 가장 가까운 음식 사이의 최단 거리 https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net 조건 정보섬 2층 0: 빈 복도 -> 지나갈 수 있음. 1: 장애물 -> 지나갈 수 없음. 2: 식구 3: 청국장 4: 스시 5: 맥앤치즈 2, 3, 4, 5는 지나갈 수 있다. 윌리암슨수액빨이딱따구리 단위 시간마다 ..
접근 각 game_board와 table 위의 퍼즐 조각들을 (0, 0)을 기준으로 좌표를 옮기는 것까지 생각은 했지만, 해당 방법의 구현과 또한 퍼즐 조각이 회전이 가능하다는 점에서 구현이 힘들어 아래 블로그를 보고 코드를 따라치며 이해하였다. ✔️너무너무 정리가 잘되어 있어 참고하면 좋을 듯 하다! https://velog.io/@hhj3258/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C%EC%9C%84%ED%81%B4%EB%A6%AC-%EC%B1%8C%EB%A6%B0%EC%A7%80-3%EC%A3%BC%EC%B0%A8-%ED%8D%BC%EC%A6%90-%EC%A1%B0%EA%B0%81-%EC%B1%84%EC%9A%B0%EA%B8%B0 [프로그래..
문제 접근 캐릭터가 적 팀의 진영까지 가는 가장 빠른 길을 찾는 것으로, 최단 경로를 찾는 문제이다. 최단 경로를 찾는 문제의 경우 제일 먼저 BFS가 떠오른다! DFS의 경우 재귀함수를 호출하여 스택을 사용하므로 구조상 모든 경로를 다 탐색해보아야 하므로 BFS에 비해 시간이 오래 걸린다. BFS를 이용하여 최단거리를 구한다! 성공 코드 각각의 위치를 구조체 Loc를 통해 구현한다. 큐에 시작 위치인 (0, 0)을 넣는다. 큐가 비어있지 않은 동안 다음을 반복한다. 큐에 들어있는 원소를 하나 pop하여 pop한 원소의 위치에서 상, 하, 좌, 우를 탐색하며 게임 맵 크기의 범위에 들어가고 방문하지 않은 위치라면 큐에 해당 위치를 넣는다. 해당 위치의 distance를 pop한 원소의 위치까지의 dist..
알고리즘 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 DFS: 시간 초과 DFS를 이용하여 최단거리를 찾고자 하는 경우 완전 탐색 후 가장 작은 값을 선택하여야 하므로 경로가 많아질 수 있고 이렇게 되면 시간 복잡도가 커진다. #include #include #include using namespace std; int map[101][101], ch[101][101], n, m; int dx[4]={1, 0, -1, 0}; int dy[4]={0, 1, 0, -1}; int cnt=1, minn=2147000000; void DFS(int x, int y){ int xx, yy, i; if(x==n && y == m){ if(cnt