🥇[백준] 1941 소문난 칠공주 (골드3) / DFS, BFS, 백트래킹

문제요약 

나의 코드 및 설명 01 - 메인 함수에 리스트 두기

• 메인 함수에 리스트를 두고 백트래킹할 시에는 반드시 append한 값을 pop해줘야 한다.

##다시풀어보기 - 메인함수에 별도의 학생 리스트 두기
from collections import deque

def bfs(seven_list):
    bfs_v = [[1]*5 for _ in range(5)] #방문 테이블 초기화. 기본값 = 1
    for i in seven_list: #리스트에 저장된 좌표 하나하나 방문하여 방문테이블 값을 0으로 바꿔준다.
        bfs_v[i[1]][i[0]] = 0
    queue = deque()
    queue.append(seven_list[0])
    bfs_v[seven_list[0][1]][seven_list[0][0]] = 1 #제일 처음 좌표는 방문 처리
    cnt = 1 #카운트도 기본 1
    while queue:
        x,y = queue.popleft()
        #네 방향을 돌아가면서 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=5 or ny>=5:
                continue
            else:
                #만약 다음 좌표가 0이라면 리스트에 저장된 좌표라는 뜻
                if bfs_v[ny][nx] == 0:
                    bfs_v[ny][nx] = 1
                    cnt += 1 #카운트 해준다
                    queue.append((nx,ny))
    #다 돌고나서 7번 다 카운트되었다면 그리드상 이어져 있는 것임
    if cnt == 7:
        return True
    else:
        return False

def dfs(count, start, Y_cnt):
    global ans
    if Y_cnt >= 4: #Y가 4가 되면 리턴(S가 4개 이상 담겨야 하므로)
        return
    
    if count == 7: #7명을 다 고르면
        if bfs(seven_list): #그 7명이 그리드 상 이어져있는지 확인
            ans+=1 #이어져있다면 ans += 1
        return
    
    for i in range(start, 25): #2차원 리스트를 1차원 리스트로. / 시작점을 start로 줌으로써 다음 선택 시 중복되지 않게
        x = i%5 
        y = i//5

        seven_list.append((x,y)) #메인 함수의 리스트 사용하니까 append, pop 메서드 사용해줘야 함
        dfs(count+1, i+1, Y_cnt+int(board[y][x] == "Y")) #넣어주는 현재 좌표 값이 Y라면 1이 추가될 것임
        seven_list.pop()


board = [list(input()) for _ in range(5)]
# v = [[0] * 5 for _ in range(5)] #dfs내에 방문 테이블 필요 없음 
#      -> 왜? 하위함수 호출 시 함수 start 파라미터 값으로 i+1 주기 때문에 

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

seven_list = [] #메인함수에 7명 학생 담을 리스트 만듬(백트래킹 시 append,pop메서드 필수)
ans = 0

dfs(0,0,0)
print(ans)

나의 코드 및 설명 02 - 함수 파라미터에 리스트 두기

• 함수의 파라미터에 특정 리스트를 두었을 때, 함수 내의 다른 함수의 변수에도 그 리스트를 활용하는 것이 가능하다는 것을 알 수 있었다.

##다시 풀어보기 - 함수 파라미터에 학생 리스트 두기
from collections import deque

def bfs(arr):
    v_bfs = [[1]*5 for _ in range(5)]
    queue = deque()
    for i in arr:
        v_bfs[i[1]][i[0]] = 0
    v_bfs[arr[0][1]][arr[0][0]] = 1
    queue.append(arr[0])
    check = 1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=5 or ny>=5:
                continue
            else:
                if v_bfs[ny][nx] == 0:
                    v_bfs[ny][nx] = 1
                    check+=1 
                    queue.append((nx,ny))
    if check == 7:
        return True
    else:
        return False

def dfs(count, start, S_cnt, temp_list):
    global ans
    if count == 7:
        if S_cnt >= 4:
            if bfs(temp_list): #(함수 파라미터의 리스트도 사용이 가능함)
                ans+=1
        return
    for i in range(start, 25):
        x = i%5
        y = i//5
        
        dfs(count+1, i+1, S_cnt+int(board[y][x] == "S"), temp_list+[(y,x)])


board = [list(input()) for _ in range(5)]

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

ans = 0

dfs(0,0,0,[])

print(ans)

피드백

풀 때는 잘 풀리지 않아 고생했지만, 다 풀고 보니 배울 점이 하나 둘이 아니었던 문제이다. 특히, 2차원 리스트 값을 무작위로 뽑기 위해 1차원 리스트로 변환 후 뽑는 방법과 dfs함수에서 고른 그리드 상의 값이 "S"인지 "Y"인지 카운트 해주는 것을 S_cnt + int(board[y][x] == "S") 를 통해 한 줄로 표현한 방법은 신선한 충격이었다. 

문제 자체는 dfs 함수로 무작위로 7명을 만들고, 그 안에서 bfs 함수를 통해 그리드 상에서 서로 이어져있는지 확인하는 문제여서 난이도가 높지는 않았던 것 같지만, DFS,BFS,백트래킹에 대한 응용력이 미흡한 것을 알 수 있었다. 골드 문제 등 난이도 있는 문제를 많이 풀어보고 응용력을 길러야겠다.