Algorithm/Baekjoon_PS 31

1063 킹 ( Simulation )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 1063 킹 - 이 문제는 시뮬레이션 문제로, 주어진 지문의 조건을 '그대로' 구현하면 되는 문제이다. - 주어진 킹과 돌의 위치를 기반으로 움직임에 대한 명령어 대로 킹과 돌을 움직여주면 된다. - 자세한 내용은 코드의 주석을 참고하자.

17141 연구소2 ( BFS, BackTracking )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 17141_연구소2 - 이 문제는 조합을 이용하여 바이러스를 선택, 선택된 바이러스를 BFS를 이용하여 확산시킴으로 전체 지도를 덮는데 얼마만큼의 시간이 걸리는지 구하는 문제이다 - 입력된 지도에서 확산시킬 수 있는 바이러스 M개의 위치를 임의의 조합으로 선정, 선정된 바이러스를 확산시켜 최종적으로 몇초가 걸리는지, 가장 적게 걸린 시간이 언제인지 구하는 문제이다. - 문제 풀이는 BFS와 백트래킹을 활용하여 풀이했다. - 자세한 내용은 코드의 주석을 참고하자.

16988_Baaaaaaaaaduk2_Easy ( BFS, BackTracking )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 16988_Baaaaaaaaaduk2_Easy - 이 문제는 조합으로 나오는 모든 경우에 대해 BFS 탐색을 이용해 풀 수 있는 문제이다 - 입력으로 주어진 바둑판 상황에 대해 "검은 돌을 두개 놓을 수 있는" 모든 경우에 대해 구하고(조합), 각 상황에 따라 흰돌 (상대의 돌)이 죽는 상황인지, 죽는다면 몇개 죽는지에 대해 BFS탐색으로 확인을 해주어 풀 수 있다. - 문제 풀이는 BFS와 백트래킹을 활용하여 풀이했다. - 자세한 내용은 코드의 주석을 참고하자.

1987_알파벳 (DFS)

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 1987_알파벳 - 이 문제는 DFS를 활용하여 이미 거쳐간 알파벳인지 확인해주는 문제 - 입력된 알파벳 배열로부터 DFS 탐색을 하며 이미 내가 사용한 알파벳인지, 내가 거쳐갔던 길인지를 확인하면서 풀이하면 된다. - 문제 풀이는 DFS와 백트래킹을 활용하여 풀이했다. - 자세한 내용은 코드의 주석을 참고하자.

17136_색종이 붙이기 ( BackTracking )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 17136_색종이 붙이기 - 이 문제는 백트래킹 방식으로 주어진 색종이를 가장 적게 사용하는 경우를 찾는 문제이다 - 입력으로 주어진 배열에서 색종이를 붙여야할 영역(1)에 대해 내가 가지고 있는 색종이를 가장 적게 사용하는 경우를 구하는 문제이다. - 문제의 로직을 이해하는 것은 어렵지 않으나 제한조건을 어떻게 줘야할지, 구현을 어떻게 해야할지 생각하는게 어려운 문제이다. - 문제 풀이는 백트래킹을 이용하여 풀이했다. - 자세한 내용은 코드의 주석을 참고하자. ( 제대로 풀이한 코드(첫번째)와 잘못 접근한 코드(두번째) 두개 모두 첨삭하였다. )

2210_숫자판점프 (DFS)

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 2210_숫자판점프 - 이 문제는 DFS를 활용하여 백트래킹 조건을 잘 세우면 풀 수 있는 문제이다. - 입력된 숫자판으로부터 만들 수 있는 6자리 숫자를 모두 구하면 되는 문제이다. - 문제 풀이는 DFS와 백트래킹을 이용하여 풀이했다. - 자세한 내용은 코드의 주석을 참고하자.

9663_N-Queen (DFS)

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 9663_N-Queen - 이 문제는 DFS로 입력받은 배열(체스판)을 전체 탐색하며, 주어진 퀸을 놓을 수 있는 모든 경우를 찾는 문제이다. - 백트래킹으로 유명한 문제이니만큼 탈출조건을 어떻게 세우냐가 관건이다. 이 문제에서는 퀸이 겹쳐지는 경우를 파악하고 접근하면 쉽게 풀이할 수 있다. ( 다만 글쓴이는 그것을 잘 해내지 못했었다 ㅎ) - 문제 풀이는 DFS를 이용하여 해결했다. - 자세한 내용은 코드의 주석을 참고하자.

9466_텀프로젝트 (DFS)

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 9466_텀프로젝트 - 이 문제는 DFS를 활용하여 사이클을 찾는 문제이다 - 입력된 순서와 학생 정보를 토대로 노드의 연결관계가 주어지고, 이를 통해 사이클을 찾은 뒤 사이클에서 제외된 학생을 수를 구하는 문제이다. 문제의 요점은 "총 학생의 수에서 제외된 학생의 수"를 구하는 것이다. - 문제 풀이는 DFS를 이용하여 해결했다. - 자세한 내용은 코드의 주석을 참고하자.

11725_트리의 부모찾기 (DFS)

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 11725_트리의부모찾기 - 이 문제는 DFS를 활용하여 "트리에 속한 각 노드"의 부모를 찾는 문제이다. - 트리의 루트는 1로 고정되어 있으니 입력값만을 생각하여 그래프로 착각해서는 안된다 - 문제 풀이는 DFS를 이용하여 풀이했다. - 자세한 내용은 코드의 주석을 참고하자.

10451_순열사이클 (BFS)

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다. 10451_순열사이클 - 이 문제는 DFS를 활용하여 사이클을 찾는 문제이다 - 입력 순서(index N) 입력값 (input M ) 이 연결방향을 뜻하며 ( N->M ) 이 관계를 이용해 입력된 순열에서 사이클을 이루는 개수를 찾는 문제이다. - 사이클에 대한 정확한 개념을 익히고 문제풀이를 하길 바란다. - 문제 풀이는 DFS를 이용해 풀이하였다. - 자세한 내용은 코드의 주석을 참고하자.