3. DFS/BFS

1. 그래프

(1) 인접 행렬 방식

- 2차원 배열로 그래프의 연결 관계를 표현하는 방식

INF = 999999999

graph = [
    [0,7,5], #0번 노드는 0번 노드와 거리가 0, 1번 노드와 거리가 7, 2번 노드와 거리가 5
    [7,0,INF], #1번 노드는 0번 노드와 거리가 7, 1번 노드와 거리가 0, 2번 노드와 연결되어있지 않음
    [5,INF,0] #2번 노드는 0번과 거리가 5, 1번 노드와는 연결되어있지 않음, 2번 노드와 거리가 0
]

- 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨

 

(2) 인접 리스트 방식

- 리스트로 그래프의 연결 관계를 표현하는 방식

INF = 999999999

graph = [
    [(1,7),(2,5)], #0번 노드는 1번 노드와 거리가 7, 2번 노드와 거리가 5
    [(0,7)], #1번 노드는 0번 노드와 거리가 7
    [(0,5)] #2번 노드는 0번 노드와 거리가 5
]

- 연결된 정보만 저장하기 때문에 메모리 효율적 사용 가능

=> 하지만, 인정 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

 

2. DFS

- Depth-First Search, 깊이 우선 탐색 : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

출처 : 위키피디아

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

 

3. BFS

- Breadth First Search, 너비 우선 탐색 : 가까운 노드부터 탐색하는 알고리즘

=> 큐 자료구조를 이용하자

- DFS보다 대체적으로 빠른 편이다.

출처 : 위키피디아

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])

    visited[start] = True

    while(queue):
        now = queue.popleft()

        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

 

1. 음료수 얼려 먹기

- N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다

 

<입력 조건>

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

<출력 조건>

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

입력 예시 4 5 00110 00011 11111 00000	출력 예시 3
입력 예시 15 14 00000111100000 11111101111110 11011101101110 11011101100000 11011111111111 11011111111100 11000000011111 01111111111111 00000000011111 01111111111000 00011111111000 00000001111000 11111111110011 11100011111111 11100011111111	출력 예시 8

 

import sys

move = [[1,0],[-1,0],[0,1],[0,-1]]

n,m = map(int, sys.stdin.readline().rstrip().split())

ice = []

for _ in range(n):
    ice.append(list(map(int,list(sys.stdin.readline().rstrip()))))

visited = [[False for _ in range(m)] for _ in range(n)]

def dfs(graph, nowx,nowy, visited):
    visited[nowy][nowx] = True

    for mx, my in move:
        dx = mx + nowx
        dy = my + nowy

        if dx<0 or dx>=m or dy<0 or dy>=n:
            continue

        if not visited[dy][dx] and graph[dy][dx] == 0:
            dfs(graph,dx,dy,visited)
            
count = 0

for y in range(n):
    for x in range(m):
        if not visited[y][x] and ice[y][x] == 0:
            count += 1
            dfs(ice,x,y,visited)

print(count)

 

2. 미로 탈출

- N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

<입력 조건>

첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

<출력 조건>

첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시 5 6 101010 111111 000001 111111 111111

출력 예시 10

import sys
from collections import deque

move = [[1,0], [-1,0], [0,1], [0,-1]]

n,m = map(int, sys.stdin.readline().rstrip().split())

maze = []

for _ in range(n):
    maze.append(list(map(int,list(sys.stdin.readline().rstrip()))))

visited = [[0 for _ in range(m)] for _ in range(n)]


def bfs(maze, visited):
    queue = deque([[0,0]])

    visitied[0][0] = 1

    while queue:
        nowy, nowx = queue.popleft()

        for my,mx in move:
            dy = nowy+my
            dx = nowx + mx

            if dy<0 or dy>=n or dx<0 or dx>=m:
                continue

            if maze[dy][dx] == 1 and visited[dy][dx] == 0:
                visited[dy][dx] = visited[nowy][nowx] + 1
                queue.append([dy,dx])

bfs(maze,visited)

print(visited[n-1][m-1])

 

3. 특정 거리의 도시 찾기

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

18352번: 특정 거리의 도시 찾기

import sys
from collections import deque

n,m,k,x = map(int,sys.stdin.readline().rstrip().split())

graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for _ in range(m):
    a,b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)

def bfs(graph, start, visited):
    queue = deque([start])

    visited[start] = 1

    while queue:
        now = queue.popleft()

        for i in graph[now]:
            if visited[i] == 0 or visited[i]>visited[now]+1:
                queue.append(i)
                visited[i] = visited[now] + 1

bfs(graph, x, visited)

result = []

for i in range(1,n+1):
    if visited[i] == k+1:
        result.append(i)

if len(result) == 0:
    print(-1)
else:
    for i in result:
        print(i)

 

4. 연구소

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

14502번: 연구소

import sys
import itertools
from collections import deque

n,m = map(int,sys.stdin.readline().rstrip().split())

maps = []

for _ in range(n):
    maps.append(list(map(int,sys.stdin.readline().rstrip().split())))

move = [[1,0], [-1,0], [0,1], [0,-1]]

wall = []

for y in range(n):
    for x in range(m):
        if maps[y][x] == 0:
            wall.append([y,x])

walls = list(itertools.combinations(wall,3))

def bfs(maps, startx, starty, visited):
    queue = deque([[starty, startx]])
    visited[starty][startx] = 1

    while queue:
        nowy, nowx = queue.popleft()

        for my, mx in move:
            dy = my + nowy
            dx = mx + nowx

            if dy<0 or dy>=n or dx<0 or dx>=m :
                continue

            if visited[dy][dx] == 0 and maps[dy][dx] == 0:
                visited[dy][dx] = visited[nowy][nowx] + 1
                queue.append([dy,dx])

answer = 0

for w in walls:
    for ty,tx in w:
        maps[ty][tx] = 1

    visited = [[0 for _ in range(m)] for _ in range(n)]
    
    for y in range(n):
        for x in range(m):
            if visited[y][x] == 0 and maps[y][x] == 2:
                bfs(maps, x, y,visited)
    
    maximum = 0

    for i in range(n):
        maximum += visited[i].count(0)
        maximum -= maps[i].count(1)

    if maximum > answer:
        answer = maximum

    for ty,tx in w:
        maps[ty][tx] = 0

print(answer)

 

5. 경쟁적 전염

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

18405번: 경쟁적 전염

import sys
import heapq

n,k = map(int,sys.stdin.readline().rstrip().split())

maps = []
for _ in range(n):
    maps.append(list(map(int,sys.stdin.readline().rstrip().split())))

s,xx,yy = map(int,sys.stdin.readline().rstrip().split())

move = [[1,0], [-1,0], [0,1], [0,-1]]

def bfs(maps,viruses, ax, ay, s):
    priority_q = []

    for y,x,v in viruses:
        heapq.heappush(priority_q, [0,v,y,x])
    
    while priority_q:
        time,virus,nowy,nowx = heapq.heappop(priority_q)

        if time>=s:
            return maps

        for my,mx in move:
            dy = my+nowy
            dx = mx+nowx

            if 0<=dy<n and 0<=dx<n and maps[dy][dx] == 0:
                maps[dy][dx] = virus
                heapq.heappush(priority_q,[time+1,virus,dy,dx])

    return maps

viruses = []

for y in range(n):
    for x in range(n):
        if maps[y][x] != 0:
            viruses.append([y,x,maps[y][x]])


maps = bfs(maps,viruses, yy-1, xx-1, s)
print(maps[xx-1][yy-1])

 

6. 괄호 변환

https://programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

def func(p):
    if len(p) == 0:
        return p
    u = None
    v = None
    
    dfs = [0 for _ in range(len(p))]
    if p[0] == '(':
        dfs[0] = 1
    else:
        dfs[0] = -1
        
    for i in range(1,len(p)):
        if p[i] == '(':
            dfs[i] = dfs[i-1] + 1
        else:
            dfs[i] = dfs[i-1] - 1
            
        if dfs[i] == 0:
            u = p[:i+1]
            v = p[i+1:]
            break
    if u == None:
        u = p
        
    if min(dfs[:len(u)+1]) < 0:
        answer = ['('] + func(v) + [')']
        
        for i in range(1,len(u)-1):
            if u[i] == '(':
                answer.append(')')
            else:
                answer.append('(')
        return answer
    else:
        return u + func(v)
        

def solution(p):
    answer = ''.join(func(list(p)))
    return answer

=> 이건 솔직히 DFS/BFS 유형인지 모르겠다.

 

7. 연산자 끼워넣기

(1) itertools 사용하는 방법 => pypy로 해야 시간 통과가 된다.

import sys
import itertools
import math

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
iterator = list(map(int,sys.stdin.readline().rstrip().split()))
iterator_list = ['+', '-', '*','/']
i_list = []

for i in range(4):
    for _ in range(iterator[i]):
        i_list.append(iterator_list[i])

it_permutations = list(itertools.permutations(i_list, len(i_list)))

minimum = math.inf
maximum = -math.inf

for now_it in it_permutations:
    answer = numbers[0]

    for i in range(len(now_it)):
        if now_it[i] == '+':
            answer += numbers[i+1]
        elif now_it[i] == '-':
            answer -= numbers[i+1]
        elif now_it[i] == '*':
            answer *= numbers[i+1]
        else:
            if answer < 0:
                answer = -(-(answer) // numbers[i+1])
            else:
                answer = answer // numbers[i+1]
    
    if answer < minimum:
        minimum = answer
    
    if answer > maximum:
        maximum = answer

print(maximum)
print(minimum)

 

(2) DFS 사용하는 방법 => 훨씬 빠르다

import sys
import math

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
iterator = list(map(int,sys.stdin.readline().rstrip().split()))

def dfs(now_result, left_iterator, index):
    if left_iterator.count(0) == 4:
        return [now_result]
    answer = []
    if left_iterator[0] > 0:
        left_iterator[0] -= 1
        answer += dfs(now_result + numbers[index], left_iterator, index+1)
        left_iterator[0] += 1

    if left_iterator[1] > 0:
        left_iterator[1] -= 1
        answer+= dfs(now_result - numbers[index], left_iterator, index + 1)
        left_iterator[1] += 1

    if left_iterator[2] > 0:
        left_iterator[2] -= 1
        answer+= dfs(now_result * numbers[index], left_iterator, index + 1)
        left_iterator[2] += 1


    if left_iterator[3] > 0:
        left_iterator[3] -= 1
        if now_result < 0 :
            answer+= dfs(-(-(now_result) // numbers[index]), left_iterator, index + 1)
        else:
            answer+= dfs(now_result // numbers[index], left_iterator, index + 1)
        left_iterator[3] += 1

    return answer

answer = dfs(numbers[0], iterator, 1)
print(max(answer))
print(min(answer))

 

8. 감시 피하기

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

18428번: 감시 피하기

 

import sys
import itertools

n = int(sys.stdin.readline().rstrip())
obstacles = []
teachers = []
maps = []
move = [[1,0],[-1,0],[0,1],[0,-1]]
for i in range(n):
    maps.append(list(sys.stdin.readline().rstrip().split()))

    for x in range(n):
        if maps[i][x] == 'X':
            obstacles.append([i,x])
        elif maps[i][x] == 'T':
            teachers.append([i,x])

o_combinations = list(itertools.combinations(obstacles,3))


for now_obstacles in o_combinations:
    for y,x in now_obstacles:
        maps[y][x] = 'O'
    
    answer = True

    for ty, tx in teachers:
        for my, mx in move:
            dy,dx = ty+my,tx+mx

            while 0<=dy<n and 0<=dx<n:
                if maps[dy][dx] == 'S':
                    answer = False
                    break
                elif maps[dy][dx] == 'O':
                    break

                dy += my
                dx += mx

    if answer == True:
        print("YES")
        exit()

    
    for y,x in now_obstacles:
        maps[y][x] = 'X'

print("NO")

 

9. 인구 이동

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

16234번: 인구 이동

import sys
sys.setrecursionlimit(1000000)
def dfs(graph, visited, nowy, nowx):
    answer = []

    for nexty, nextx in graph[nowy][nowx]:
        if visited[nexty][nextx] == 0:
            visited[nexty][nextx] = 1
            answer.append([nexty,nextx])
            answer += dfs(graph,visited,nexty,nextx)
    
    return answer


n,l,r = map(int,sys.stdin.readline().rstrip().split())
lands = []

for _ in range(n):
    lands.append(list(map(int,sys.stdin.readline().rstrip().split())))

move = [[1,0],[0,1]]

count = 0
while True:
    graph = [[[] for _ in range (n)] for _ in range(n)]
    check_bool = False
    for y in range(n):
        for x in range(n):
            for my,mx in move:
                dy = my+y
                dx = mx+x

                if 0<=dy<n and 0<=dx<n:
                    if l<=abs(lands[y][x] - lands[dy][dx])<=r:
                        check_bool = True
                        graph[y][x].append([dy,dx])
                        graph[dy][dx].append([y,x])
    
    if check_bool == False:
        break
    else:
        count+= 1

    visited = [[0 for _ in range(n)] for _ in range(n)]

    for y in range(n):
        for x in range(n):
            if visited[y][x] == 0:
                result = dfs(graph,visited,y,x)

                if len(result)>0:
                    total = 0

                    for dy,dx in result:
                        total += lands[dy][dx]

                    average = total // len(result)
                    for dy,dx in result:
                        lands[dy][dx] = average

print(count)