[Python] 백준 / gold / 1941 : 소문난 칠공주
문제 링크 : https://www.acmicpc.net/problem/1941
내가 정말 DFS의 개념을 정확히 알고있나 한번 더 체크해준 문제. DFS 는 특성상 십자 모양으로 갈라지는 탐색을 하기는 어렵다. 근데 이 문제는 그런 경우를 요구하기 때문에 DFS 로 풀지 않는게 좋다. 근데 왜 이 문제의 분류가 백트래킹이냐. 25C7 의 경우를 나눠야 하기 때문에 그런 것 같다.
먼저 combinations 로 가능한 위치 7개 조합을 뽑은 뒤, 'S' 가 4개 미만이라면 거르고, 원소가 서로 인접해 있는지 BFS 로 체크해서 풀었다.
얻어갈 2가지
- DFS 탐색으로 십자 모양 갈라지는 탐색은 하기 어렵다.
- 좌표 튜플을 리스트 컴프리헨션으로 초기화 하는 방법
- 리스트 원소 타입이 boolean 인 경우는 if False in myList: 같은 문법도 사용할 수 있다.
-> 이런게 십자 모양으로 갈라지는 탐색.
파이썬 코드
from itertools import combinations from collections import deque import sys graph = [] direction = [(-1, 0), (1, 0), (0, -1), (0, 1)] positions = [(i, j) for i in range(5) for j in range(5)] combs = list(combinations(positions, 7)) answer = 0 for _ in range(5): graph.append(list(sys.stdin.readline().strip())) def checkDaSom(givenComb): daSom = 0 for x, y in givenComb: if graph[x][y] == 'S': daSom += 1 return True if daSom >= 4 else False def checkAdjacent(givenComb): visit = [False]*7 q = deque() q.append(givenComb[0]) visit[0] = True while q: x, y = q.popleft() for d in direction: nx = x + d[0] ny = y + d[1] if (nx, ny) in givenComb: nextIdx = givenComb.index((nx, ny)) if not visit[nextIdx]: q.append((nx, ny)) visit[nextIdx] = True return False if False in visit else True for comb in combs: if checkDaSom(comb): if checkAdjacent(comb): answer += 1 print(answer)
Author And Source
이 문제에 관하여([Python] 백준 / gold / 1941 : 소문난 칠공주), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heyksw/Python-백준-gold-1941-소문난-칠공주저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)