-
2667. [Python]단지번호붙이기Python_알고리즘/Silver I 2023. 6. 4. 03:37
1. 문제
https://www.acmicpc.net/problem/26672667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- DFS(너비 우선 탐색)
3. 파이썬 코드
N = int(input()) # 매트릭스 담을 리스트 matrix = [list(map(str,input())) for _ in range(N)] # 방문했는지 체크 여부 visited = [[False] * N for _ in range(N) ] # 상하좌우 움직임 dx = [-1,0,0,1] dy = [0,-1,1,0] # 총 몇개의 집이 존재하는지 저장할 리스트 total_length = [] # N*N 행렬이므로 이중 for문 생성 for i in range(N): for j in range(N): # 각 j for문마다 상하좌우 통해서 같은 1이나오는 구역 체크 stack = [] # 만약 matrix 값이 "1" 인 경우 if matrix[i][j] == "1": # 방문한 적이 없는경우 if not visited[i][j]: # 갯수 변수를 1로 선언해준 후 stack 에 리스트 형태로 추가 cnt = 1 stack.append([i,j]) # stack 값이 없어질 동안 반복문 시행 while stack: # stack 값을 뽑아서 stack_list 라는 변수에 저장 stack_list = stack.pop() # 뽑은 값의 인덱스값에 true 처리해서 방문했다고 표시 visited[stack_list[0]][stack_list[1]] = True # 상하좌우 탐색을 진행하며 0~N 값사이의 x,y 좌표일 경우 와 "1" 인경우이면서 stack에 중복되지 않을 때 stack 이라는 리스트에 추가 후 cnt 값 추가 for k in range(4): x = stack_list[1] + dx[k] y = stack_list[0] + dy[k] if (x >= 0 and x < N) and (y >= 0 and y < N): if matrix[y][x] == "1": if not visited[y][x] and [y,x] not in stack: stack.append([y,x]) cnt += 1 total_length.append(cnt) # 총 길이를 출력 후 오름차순 정렬 후 출력 print(len(total_length)) total_length.sort() for i in total_length: print(i)
4. 문제를 풀고난 후 생각
- DFS를 이용하여 문제를 해결했다.
- 한개의 영역에 방문했을 때, 그 영역을 방문했는지 판단한 후 이후 상,하,좌,우 를 탐색하며 같은 조건이 되는 경우 리스트에 x,y 값을 추가해 주는 방식으로 반복문이 없어질 때 까지 조건에 맞도록 반복문을 탐색하여 각각 몇개의 구역으로 나뉘는지 변수를 통해 체크해준다.
- 체크해준 변수를 정답 리스트에 추가한 후 오름차순 정렬을 위해서 정답 리스트를 따로 정렬해주면 해결된다.
- DFS/BFS 문제들은 보통 비슷한 유형으로 풀기 때문에 따로 정리를 통해서 한번 게시글을 작성할 예정이다.
5. 문제를 푸는데 도움이 되는 지식
- DFS(너비 우선 탐색)
- BFS(깊이 우선 탐색)
'Python_알고리즘 > Silver I' 카테고리의 다른 글
1926. [Python]그림 (0) 2023.12.09 1342. [Python]행운의 문자열 (1) 2023.12.08 1421. [Python]나무꾼 이다솜 (2) 2023.12.07 1527. [Python] 금민수의 개수 (0) 2023.08.30 1697. [Python]숨바꼭질 (0) 2023.03.09