MuviSsum

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제: 집들이 연결되어 있는 단지를 파악하고 총 단지의 수와 각 단지의 집이 몇개인지 파악하라. 문제 이해하기!! 해당 문제는 딱 명확한 완전탐색이었습니다. BFS, DFS든 상관은 없구요, visit 배열로 방문체크만 해준다면 바로 풀리는 문제입니다. 제가 푼 방식을 설명하자면, 1. 입력받은 배열을 for문으로 돌려, 아직 방문하지 않은 곳이고 집이 있는 곳이라면 DFS를 수행합니다. 2. DFS구현: DFS..

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제: 로봇 청소기가 청소하는 칸의 개수를 출력하라. 문제 이해하기!! 전형적인 구현 문제입니다. 문제에 주어진대로 따라하면 코드를 작성하면 풀 수 있는데, 다만 얼마나 효율적으로 짜냐, 어떤 방식으로 짜냐가 중요하죠!! 저는 밑의 방식으로 풀게 되었습니다. 그 방식을 설명하자면!! 1. 각 방향으로 한 칸 전진하는 것을 함수로 만들어 줍니다. 2. 주어진 행동을 계속 반복하기 위해 while True로 반복..

DFS란? 깊이 우선 탐색 자신에게 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다. 이동한 노드에서 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다. 이렇게 계속 내려가다가 자식 노드가 없는 노드를 찾는다. 다시 부모 노드로 이동하여 새로운 자식 노드를 찾는다. 또 자식노드가 없으면 다시 부모노드로 이동하여 위의 순서를 반복한다. 완전탐색 중 한 방법 - 위의 순서를 보면 모든 노드를 체크하는 것을 볼 수 있다. DFS에서 발전된 알고리즘 : 백트레킹 백트레킹은 DFS 방식을 하면서 조건을 추가한다. 한 노드가 조건에 맞지 않으면 밑의 자식노드 또한 조건에 맞지 않으므로 다시 부모노드로 돌아간다. DFS보다 훨씬 시간을 줄일 수 있다. DFS를 이해하기 위해서는 그림을 보면 쉽..