-
1388. [Python]바닥 장식Python_알고리즘/Silver IV 2023. 5. 3. 23:50
1. 문제
https://www.acmicpc.net/problem/1388
1388번: 바닥 장식
형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- DFS
3. 파이썬 코드
N,M = map(int,input().split()) # 방문 헀는지 체크하기 위한 리스트 visited = [[False] * M for _ in range(N)] cnt = 0 dx = 1 dy = 1 # 타일의 종류 tile = [input() for _ in range(N)] # 타일의 가로 세로만큼 반복문 진행 for i in range(N): for j in range(M): # stack 이라는 리스트 변수를 통해서 방문할 인덱스 체크 stack = [] # 만약 타일이 - 인경이와 ㅣ 인경우로 분리 if tile[i][j] == "-": # 타일을 방문하지 않았을 경우만 조건실행 if not visited[i][j]: # 방문했다는 표시를 남겨주고 cnt 라는 갯수변수를 1증가 visited[i][j] = True cnt += 1 # - 타일의 경우 우측으로 진행되기 때문에 우측으로 이동 x = j + dx # 만약 M길이를 넘을 경우 stack 이라는 리스트에 추가하지않음 if x < M: stack.append(x) # stack이라는 리스트에 내용물이 있을경우 반복문 실행 while stack: # stack 에서 pop해온 값을 변수로 저장 next = stack.pop() # 만약 다음 타일이 같은 - 인경우 방문했는지 체크한 후 다시 값을 1증가하고 M을 넘는지 확인 if tile[i][next] == "-": if not visited[i][next]: visited[i][next] = True x = x + dx if x < M: stack.append(x) elif tile[i][j] == "|": if not visited[i][j]: visited[i][j] = True cnt += 1 y = i + dy if y < N: stack.append(y) while stack: next = stack.pop() if tile[next][j] == "|": if not visited[next][j]: visited[next][j] = True y = y + dy if y < N: stack.append(y) print(cnt)
4. 문제를 풀고난 후 생각
- 각 문양별 조건에 따라서 우측으로 갈지 아래로 갈지 결정하는 문제였다.
- 일반 DFS(깊이 우선 탐색)과는 다르게 상하좌우를 살피는 것이 아닌 본인의 오른쪽 혹은 아래만 확인하면 되는 문제였다.
- '-'가 나왔을 경우 우측으로 한칸가서 똑같은지 다른지 판단하고 같으면 리스트에 값을 추가해 나가서 리스트가 비어있을 때까지 반복문을 선언해주면 된다.
- 'ㅣ'인 경우도 위와 마찬가지로 아래로 한칸만 확인해서 계속 진행해주면 된다.
- 막히지 않고 끝까지 도달했을 경우도 생각하여 만약 N,M 에 각각 크기가 같아질 경우도 체크해주고 visited라는 리스트를 통해서 방문 했는지 안했는지를 체크해주면 쉽게 풀 수 있는 문제이다.
5. 문제를 푸는데 도움이 되는 지식
- DFS
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1758. [Python]알바생 강호 (0) 2023.05.11 1487. [Python]물건 팔기 (0) 2023.05.04 1246. [Python]온라인 판매 (0) 2023.04.30 2003. [Python]수들의 합 2 (0) 2023.04.18 1639. [Python]행운의 티켓 (0) 2023.04.17