[백준 1941] 소문난 칠공주

https://www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

 

li = [ input() for _ in range(5) ]
delta = [ (-1,0), (1,0), (0,-1), (0,1) ]
res_set = set()

# 백트래킹
# arr: 지금까지 거쳐간 좌표 리스트, s: 이다솜파 수, y: 임도연파 수
def bt(arr, s, y): 
    if y > 3: # 임도연파 수가 다수이므로 탐색을 종료 
        return
    if (len(arr) - 1) == 6: # 7번의 탐색을 마쳤고 이다솜파가 다수이면, 
        arr.sort() # 현재까지 거쳐간 좌표들을 정렬 후 (좌표의 순서는 상관없고 유일을 보장하기 위해)
        res_set.add(tuple(arr)) # 결과 집합에 추가 (set 으로 중복 제거) 
    else:
        adjs = [] # 인접 좌표들 리스트
        
        for node in range(len(arr)): # 현재까지 거쳐간 좌표들의 인접 좌표를 체킹 
            for i in range(4): # 인접 상하좌우 체크 
                dx = arr[node][0] + delta[i][0]
                dy = arr[node][1] + delta[i][1]

                if not ( 0 <= dx < 5 and 0 <= dy < 5 ): # 범위를 벗어나는 좌표 패스 
                    continue
                if (dx, dy) in arr: # 현재까지 거쳐간 좌표이면 있으면 패스 
                    continue
                adjs.append((dx, dy)) # 탐색하기 위해 추가
        
        # 추가된 인접 좌표들중에 이다솜파이면 s 추가 후 탐색, 임도연파면 y 추가 후 탐색 
        for adj in adjs:
            nx = adj[0]
            ny = adj[1]
            if li[nx][ny] == 'S':
                bt(arr + [(nx, ny)], s + 1, y)
            else:
                bt(arr + [(nx, ny)], s, y + 1)

for i in range(5):
    for j in range(5):
        if li[i][j] == 'S': # 첫 이다솜파를 만날 시 탐색을 시작하므로 s는 1부터 시작 
            bt([(i, j)], 1, 0)

print(len(res_set))

먼저 마지막 풀이를 보면 각 좌표를 돌면서 이다솜파를 만나면 백트래킹을 시작하게 된다. 

 

이때 백트래킹 함수(bt)의 인수로 arr는 현재까지 거쳐온 좌표 리스트, idx는 0부터 시작하는 현재까지 거쳐온 bt 횟수... 인데 그냥 arr의 길이 - 1 해도 됐었네.. 아니면 s+y-1 해도 되고. 암튼 s는 이다솜파의 수, y는 임도연파의 수. 또 s, y 나눌 것도 없이 그냥 len(arr) - s 하면 y 구나 아니 그냥 y 인수가 필요가 없네

 

bt의 가치지기 조건으로 임도연파의 수가 다수가 되는 조건 (y > 3) 이면 함수를 종료하도록 했다. 

또 idx가 6이면 7번의 탐색을 마쳤고 이다솜파가 다수라는 뜻이므로, 지금까지 거쳐온 좌표 리스트를 정렬함으로써 순서가 다르지만 요소는 다른 값들을 똑같은 리스트로 만들어준 뒤 Set 에 넣어줌으로써 중복을 제거한다. 

 

그리고 아직 7번의 탐색을 마치지 않았다면, 지금까지 거쳐온 좌표 리스트의 좌표들 중에 그 인접 좌표들을 큐에 넣어주는데, 좌표 범위를 넘거나 기존에 다녀온 좌표이면 패스한다. 

 

그렇게 완성된 인접 좌표 리스트를 DFS로 도는데, 먼저 인접 좌표를 arr에 추가하고, idx도 +1 추가하고,  그 인접 좌표가 이다솜파면 s를, 임도연파면 y를 +1 하여 돌린다. 

 

 

---

 

 

다른 풀이로는 (x, y) 튜플로 구성된 좌표 리스트중에서 조합으로(순서가 상관없으니) 7개를 뽑아서 리스트를 구성하고, 7개 중에 이다솜파가 다수인 요소들만 1차로 필터링하고, 그중에 각 좌표가 이어져 있는지 2차로 필터링 하는 방법으로 구하는 풀이가 있는데 위의 풀이가 더 빠르다. 

 

 

참고 링크

1

[백준] 1941 소문난 칠공주 python

 

2

[Python] 백준 / gold / 1941 : 소문난 칠공주

---

 

1. 파이썬의 이중포문 break 방법 2개

2. DFS는 십자모양 탐색은 하기 어렵다

3. 2차원 배열말고 1차원으로 y = idx//5, x = idx % 5 로 할 수도 있따

 

 

파이썬의 이중 for문 break 방법

 

1. break 체크 변수 추가

li = [ [0] * 5 ] * 5
is_break = False
print(li)

for i in range(5):
    for j in range(5):
        if j > 2:
            is_break = True
            print("break")
            break
        print(i, j)
    if is_break:
        print("break")
        break

[
	[0, 0, 0, 0, 0], 
	[0, 0, 0, 0, 0], 
	[0, 0, 0, 0, 0], 
	[0, 0, 0, 0, 0], 
	[0, 0, 0, 0, 0]
]
0 0
0 1
0 2
break
break

2. 예외처리

try:
    for i in range(5):
        for j in range(5):
            if j > 2:
                raise NotImplementedError
            print(i, j)
except:
    print('end')