dfs

오랜만에 알고리즘 문제 푸려니까 죽을 맛이네요 영역 구하기 성공 문제 눈금의 간격이 1인 M×N(M, N≤100) 크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프..

안녕하세요 오늘은 파이썬으로 푸는 간단한 DFS 문제를 소개해드립니다. DFS자체가 간단한 알고리즘은 아니지만 이해하신 분들에게는 쉬우며 아직 이해 도중에 있는 분들은 연습 삼아 풀어볼 만한 문제인 것 같네요. 문제 n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 아래와 오른쪽 2방향 중 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 과 같이 뱀이 배치되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요. 입력 형식 첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 ..