백준 1941 : 소문난 칠공주(Python)

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

1941번: 소문난 칠공주

https://github.com/HPYoo/swcodingtest/commit/1419fd7bf8adc58737e0b8972b893870ea3f79e2

sw coding 1941 update(Baekjoon) · HPYoo/swcodingtest@1419fd7

1. 조합함수 이용하기

 아직 백트래킹, DFS에 익숙하지 않아서 조합을 활용하여 문제를 풀었다. 

조합 배열 구하면서 크기가 4이상일 때 임도연파("Y")가 4개 이상 점유하게 되면 저장을 안하도록 하였다. 이렇게 하면 예제를 기준으로 하였을 때 48만여개의 데이터가 6000여개로 줄어서 서로 붙어있는지 확인할 때 시간을 최대한 단축할 수 있도록 하였다.

def combination(arr, t):
    result = []
    if t == 0 : return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[i + 1 : ]
        for C in combination(rest_arr, t - 1):
            temp = [elem] + C
            if len(temp) >= 4 :
                cnt = 0
                for k in range(len(temp)):
                    if board[temp[k][0]][temp[k][1]] == 'Y' : cnt += 1
                if cnt >= 4 : continue
            result.append([elem] + C)
    return result

2. 붙어있는지 조사할 때 추출한 변수만 가지고 확인하기

 최근 BFS 문제를 풀면서 5x5배열을 통째로 검사하는 게 습관이 되다보니 시간초과라는 판정을 계속 받게 되었다. 

실제로는 추출한 7개의 리스트만 가지고 그래프 탐색하면 된다. 그래프 탐색은 검사할 리스트의 인덱스를 활용하여 방문처리 하면 된다. 그렇게 되면 7번안에 검사가 끝나게 된다. 사고를 여유롭게 하도록 하자.

3. 전체 코드

 메모리 : 248788 KB, 시간 : 3016 ms (1초 오버), 풀이시간 : 85 min

 ※ 여기서 itertools 이용해서 코드를 짜면 메모리 : 176988 KB, 풀이시간 : 684 ms 로 줄어들게 된다. 

 ※ 나름 고집이긴 한데.. 학과 수업때도 패키지 안쓰고 코드 짜는 연습을 했었던 터라, 패키지를 최대한 안쓰고 풀려고 한다.

from collections import deque
board = [list(map(str, input())) for _ in range(5)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def combination(arr, t):
    result = []
    if t == 0 : return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[i + 1 : ]
        for C in combination(rest_arr, t - 1):
            temp = [elem] + C
            if len(temp) >= 4 :
                cnt = 0
                for k in range(len(temp)):
                    if board[temp[k][0]][temp[k][1]] == 'Y' : cnt += 1
                if cnt >= 4 : continue
            result.append([elem] + C)
    return result
info = []
for i in range(5):
    for j in range(5):
        info.append([i, j])

comb = deque(combination(info, 7))

def bfs():
    result = 0
    while comb :
        temp = comb.popleft()
        visited = [False for _ in range(7)]
        q = deque([temp[0]])
        visited[0] = True
        while q :
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < 5 and 0 <= nx < 5 :
                    if [nx, ny] in temp :
                        idx = temp.index([nx, ny])
                        if not visited[idx] :
                            visited[idx] = True
                            q.append([nx, ny])
        if False not in visited :
            result += 1
    return result

print(bfs())