이것이 취업을 위한 코딩 테스트다 CHAPTER 13 DFS/BFS 문제

Q 15. 특정 거리의 도시 찾기

'''

    Chapter 13. 특정 거리의 도시 찾기

    접근법 1

        최단 거리 구하는 문제 -> bfs

        현 위치에서 갈 수 있는 도시를 다 방문

            최단 거리보다 더 적은 거리로 방문했으면 방문 이어서 하기

            최단 거리로 방문했으면 그 이상 방문은 최단거리보다 크기 때문에 그 도시에서 더 나아가지 않기

'''

from collections import deque
import sys
input = sys.stdin.readline

# 도시의 개수, 도로의 개수, 거리정보(최단거리),출발도시번호
N,M,K,X = map(int,input().split())
# 도로
load = [[] for _ in range(N)]
for _ in range(M):
    A,B = map(int,input().split())
    load[A-1].append(B-1)

# 방문 표시
visited = [0]*N
que = deque()
# 시작점
visited[X-1] = 1
que.append([X-1,0])

# 최단거리가 K인 도시들
answer = []

while que:
    # 현 위치, 이동 거리
    current, dist = que.popleft()
    # 이동
    # 현 위치에서 이동할 수 있는 도시
    for i in load[current]:
        # 방문한 적 없다면
        if visited[i] == 0:
            # 방문
            visited[i] = 1
            # 최단거리가 K인 도시인가?
            if dist+1 == K:
                answer.append(i+1)
            # 최단거리가 K보다 크면 더 방문할 필요X
            # 최단거리가 K보다 작을 때만 이동
            elif dist+1 < K:
                que.append([i,dist+1])

# 정답 출력
if answer:
    for a in sorted(answer):
        print(a)
else:
    print(-1)

 

Q 16. 연구소

'''

    Chapter 13. 연구소

    접근법 1

        목표 : 벽 3개 세운 후 안전 영역의 최대 크기 구하기

        지도의 크기 최대 8*8이므로 벽 3개를 세우는 모든 경우의 안전 영역 크기 구하기

            벽 3개 세우기 : 완전 탐색

            안전 영역 크기 세기 : DFS

'''

from itertools import combinations
from copy import deepcopy
import sys
input = sys.stdin.readline

# 지도의 세로, 가로
N,M = map(int,input().split())
# 지도 (0:빈칸, 1:벽, 2: 바이러스)
arr = [list(map(int,input().split())) for _ in range(N)]

# 빈칸의 위치
empty = []
# 바이러스 위치
virus = []
for r in range(N):
    for c in range(M):
        if arr[r][c] == 0:
            empty.append([r,c])
        elif arr[r][c] == 2:
            virus.append([r,c])

# 안전 영역 기본값
safe_default = len(empty)
# 안전 영역 최댓값
answer = 0

# 빈칸 3개 고르기
for c in combinations(empty,3):
    temp = deepcopy(arr)
    # 빈칸 3개를 벽으로 바꾸기
    for i,j in c:
        temp[i][j] = 1

    # 현재 경우 안전 영역 크기
    cnt = safe_default-3

    # 방문 체크
    visited = [[0]*M for _ in range(N)]
    
    # 바이러스 퍼트리기
    for vr,vc in virus:
        # 방문
        visited[vr][vc] = 1
        stack = [[vr,vc]]
        while stack:
            # 현 위치
            cr,cc = stack.pop()
            # 이동
            for dr,dc in [[0,1],[-1,0],[1,0],[0,-1]]:
                nr = cr+dr
                nc = cc+dc
                # 범위내, 방문한 적 없는 빈칸
                if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == 0 and temp[nr][nc] == 0:
                    cnt -= 1
                    visited[nr][nc] = 1
                    temp[nr][nc] = 2
                    stack.append([nr,nc])
    answer = max(cnt,answer)

print(answer)

과거 풀이

https://chaemi720.tistory.com/173

[백준] 14502. 연구소 - Python

 

Q 17. 경쟁적 전염

 

https://chaemi720.tistory.com/277

[백준] 18405. 경쟁적 전염 - Python (BFS 사용 X)

 

Q 18. 괄호 변환

'''

    Chapter 13. 괄호 변환

    접근법 1

        단계가 있다 -> 구현/시뮬레이션

        두 문자열로 분리

            -> 여는 괄호 수와 닫는 괄호 수가 같을 때 stop

        올바른 괄호인지

            여는 괄호와 닫는 괄호가 세트인지 확인해야함

            -> 닫는 괄호가 나왔을 때 이전에 여는 괄호가 있었는지만 확인하면 됨

            -> 이미 균형잡힌 괄호이기 때문에

            DFS를 사용할 수도 있음

'''

# 올바른 괄호 문자열인지 확인하는 함수
def correct_check(p):
    cor = 0
    for i in p:
        # 여는 괄호
        if i == '(':
            cor += 1
        # 닫는 괄호
        else:
            # 여는 괄호가 없는데 닫는 괄호가 나온 경우
            if cor == 0:
                return False
            cor -= 1
    # 균형잡힌 괄호 문자열이므로 남은 괄호 없음
    return True

'''
# 올바른 괄호 문자열 DFS 사용하는 경우
def correct_check(p):
    stack = []
    for i in p:
        # 여는 괄호
        if i == '(':
            stack.append(i)
        # 닫는 괄호
        else:
            # 여는 괄호가 있어야 함
            if stack:
                stack.pop()
            else:
                return False
    # 균형잡힌 괄호 문자열이므로 남은 괄호 없음
    return True                
'''
    
# 두 문자열로 분리
def two_split(p):
    l = r = 0
    for i in range(len(p)):
        if p[i] == '(':
            l += 1
        else:
            r += 1
        # 균형잡힌 괄호 문자열인가?
        if r == l:
            return p[:i+1],p[i+1:]

        
def solution(p):
    # 1. 빈 문자열인 경우
    if p == '':
        return p
    
    # 2. 문자열 2개로 분리
    u,v = two_split(p)
    # 3. u가 올바른 괄호이면 v에 대해 solution(v)
    if correct_check(u):
        # 3-1. u와 붙인 후 return
        return u + solution(v)
    
    # 4. u가 올바른 괄호가 아니면
    else:
        # 4-1~4-3
        new_v = '(' + solution(v) + ')'
        # 4-4. u의 첫번째 마지막 제거하고, 나머지 뒤집기
        new_u = ''
        for j in u[1:-1]:
            if j == '(':
                new_u += ')'
            else:
                new_u  += '('
        # 4-5
        return new_v + new_u

 

Q 19. 연산자 끼워 넣기

'''

    Chapter 13. 연산자 끼워넣기

    접근법 1

        4가지 연산 다 생각해야 함 -> 완전 탐색

        연산 끝까지 진행 후 다음 경우 구해야 함 -> DFS 재귀

        '나누기'의 경우 음수 생각

            ex) -12 나누기 5 는 -(-(-12)나누기5의 몫))로 계산해서 -2가 답

                -12//5 == 3

                -12/5 == -2.4

                int(-12/5) == -2

   

'''

import sys
input = sys.stdin.readline

# 수의 개수
N = int(input())
# 수
number = list(map(int, input().split()))
# 연산자 수 (덧셈,뺄셈,곱셈,나눗셈)
plus, minus, mul, div = map(int, input().split())

# 결과 최대
max_answer = float('-inf')
# 결과 최소
min_answer = float('inf')

# 완전 탐색
def cal(i,num,plus,minus,mul,div):
    global max_answer,min_answer
    # 연산 끝
    if i == N:
        max_answer = max(max_answer,num)
        min_answer = min(min_answer,num)
        return 
    
    # 더하기
    if plus:
        cal(i+1, num+number[i], plus-1, minus, mul, div)
    # 빼기
    if minus:
        cal(i+1, num-number[i], plus, minus-1, mul, div)
    # 곱하기
    if mul:
        cal(i+1, num*number[i], plus, minus, mul-1, div)
    # 나누기
    if div:
        cal(i+1, int(num/number[i]), plus, minus, mul, div-1)

cal(1,number[0],plus,minus,mul,div)

print(max_answer)
print(min_answer)

 

Q 20. 감시 피하기

'''

    Chapter 13. 감시 피하기

    접근법 1

        목표 : 3개의 장애물을 설치해서 감시를 피하자    

   

        복도의 최대 크기 36, 장애물 3개 설치하는 최대 경우의 수 -> 36C3

        -> 완전 탐색

        장애물 3개 설치 후 선생님마다 4방향을 다 확인해본다

            확인하던 중 장애물 or 다른 선생님을 만나면 그 방향으로 확인 멈추기

            학생을 만나면

                다음 장애물 3개 설치 경우로 넘기기

       

'''

from itertools import combinations
from copy import deepcopy
import sys
input = sys.stdin.readline

# 3개의 장애물을 설치해서 감시로부터 피해라

# 복도 크기
N = int(input())
# 복도
arr = [list(input().split()) for _ in range(N)]

# 빈칸 위치
empty = []
# 선생님 위치
teacher = []
for r in range(N):
    for c in range(N):
        if arr[r][c] == 'T':
            teacher.append([r,c])
        elif arr[r][c] == 'X':
            empty.append([r,c])

# 감시
def check(temp):
    for tr,tc in teacher:
        # 4방향 확인
        for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:
            nr = tr+dr
            nc = tc+dc
            while 0<=nr<N and 0<=nc<N:
                # 감시방향에 장애물 or 다른 선생님이 있는 경우 그 쪽 안봐도 됨
                if temp[nr][nc] == 'O' or temp[nr][nc] == 'T':
                    break
                # 학생 발견?
                if temp[nr][nc] == 'S':
                    return False
                # 감시방향으로 다음 칸 보기
                nr += dr
                nc += dc
    return True


# 빈칸 3개 설치
for install in combinations(empty,3):
    temp = deepcopy(arr)
    for i,j in install:
        temp[i][j] = 'O'

    # 감시에서 피할 수 있는가
    if check(temp):
        print('YES')
        exit(0)

# 모든 경우 감시를 피할 수 없었다.
print('NO')

 

Q 21. 인구 이동

'''

    Chapter 13. 인구 이동

    접근법 1

        모든 나라의 인접한 나라의 인구수를 확인한 뒤 연합을 만들어 인구 이동 처리

        인구이동을 할 수 없을 때까지

        -> bfs

        인구이동이 있었는지(== 연합이 있었는지)를 flag 변수를 통해 확인

'''

from collections import deque
import sys
input = sys.stdin.readline

# 땅의 크기, L명이상 R명 이하
N,L,R = map(int,input().split())
# 인구수
population = [list(map(int,input().split())) for _ in range(N)]

# 연합 찾기
def bfs(r,c):
    que = deque()
    que.append([r,c])

    # (r,c)와 연결된 나라
    connect = [[r,c]]
    # 연합 전체 인구
    connect_sum = population[r][c]

    while que:
        # 현 위치
        cr,cc = que.popleft()
        # 4방향 확인
        for dr,dc in [[1,0],[-1,0],[0,1],[0,-1]]:
            nr = cr+dr
            nc = cc+dc
            # 범위 내, 확인한 적 없는 나라, 인구차이가 L명이상 R명이하
            if 0<=nr<N and 0<=nc<N and visited[nr][nc] == 0 and L <= abs(population[cr][cc]-population[nr][nc]) <= R:
                visited[nr][nc] = 1
                que.append([nr,nc])
                connect.append([nr,nc])
                connect_sum += population[nr][nc]

    # 연결된 나라 인구 이동
    for i,j in connect:
        population[i][j] = connect_sum//len(connect)
    
    # 연결된 나라 수
    return len(connect)

# 인구 이동 횟수
answer = 0
while True:
    # 인구이동이 있었는가
    flag = False

    # 확인했는지
    visited = [[0]*N for _ in range(N)]

    for r in range(N):
        for c in range(N):
            # 확인한 적 없는 나라
            if visited[r][c] == 0:
                visited[r][c] = 1
                # 연합이 있는가?
                if bfs(r,c) > 1:
                    flag = True
                
    # 인구이동 없다
    if not flag:
        break 
    # 하루 끝
    answer += 1

print(answer)

 

Q 22. 블록 이동하기

https://chaemi720.tistory.com/289

[프로그래머스] 블록 이동하기 - Python