이것저것 개발 블로그

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

문제)

해설)

이 문제는 당연히 bfs로 풀어야지!! 하면서 좀 헤맸다..ㅎㅎ

두 가지 방식으로 했는데, 코드는 두 번째가 조금 더 깔끔한 것 같다.

풀이 1)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    count = 0
    while tomato:
        second = []
        t_li = tomato.popleft()
        for t_mem in t_li:
            x, y = t_mem[0], t_mem[1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if box[nx][ny] == 0:
                        second.append([nx, ny])
                        box[nx][ny] = 1
                    else:
                        continue
        if second != []:
            tomato.append(second)
        count += 1
    return count - 1

m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

first = []
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            first.append([i, j])
tomato.append(first)


day = bfs(tomato)
for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            print(-1)
            exit(0)
print(day)

bfs 함수 내에서 며칠이나 걸렸는지 반환해주려고 이 코드를 짜게 되었다.

한 박스에 토마토가 여러 개일 경우 동시에 토마토가 있는 좌표의 옆 토마토들이 익는다.

따라서 하루 단위로 익을 토마토(box에서 0인 애들) list(first, second)를 만들어 저장하고, 그것을 tomato라는 queue에 저장하는 방식으로 구현했다.

tomato에서 하나를 뽑으면 그 list에 해당하는 좌표를 순회하고, 해당 list에 저장된 좌표를 모두 돌면 하루가 늘어나는 방식이다.

하지만 여기에는 처음에 토마토가 있던 위치도 하루가 지난 것으로 치는 방식이기에 1을 뺀 값을 반환한다.

bfs가 모두 끝나면 혹시 토마토가 익지 않은 경우가 있을 수 있기 때문에 확인해준다.

여기에서 익지 않은 토마토가 있을 경우 -1을 출력하고 exit 하여 끝낸다.

그렇지 않다면 bfs 결과를 출력해준다.

풀이 2)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    while tomato:
        x, y = tomato.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if box[nx][ny] == 0:
                    tomato.append([nx, ny])
                    box[nx][ny] = box[x][y] + 1
                else:
                    continue


m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            tomato.append([i, j])


day = 0
bfs(tomato)
for i in box:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    day = max(day, max(i))
print(day - 1)

이 풀이도 똑같이 bfs를 활용했다.

다른 점은 좌표를 차례대로 queue인 tomato에 저장해주고, bfs를 하는 도중 다음 좌표의 box 값이 0이라면 원좌표의 값에 +1을 해주는 방식을 사용했다. 

또한 이 방식도 처음 토마토의 위치가 1이어서 하루가 더 더해진 방식이므로 box에 0이 없음을 확인하면 1을 뺀 값을 출력해준다.

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

문제)

풀이)

def dfs(x):
    global visited
    if visited[x] == False:
        visited[x] = True
        for i in graph[x]:
            dfs(i)
    else:
        return 0

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
li = int(input())

for i in range(li):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

count = 0
dfs(1)
for i in range(2, len(visited)):#1번은 제외
    if visited[i] == True:
        count += 1
print(count)

이 문제는 dfs로 해결했는데, 간단한 문제이다. 물론 bfs로도 충분히 가능할 것이다.

무조건 1번에서 시작하므로 1번 노드에서 각 노드를 방문 표시한 개수를 센다면 문제를 해결할 수 있을 것이라고 생각했다.

따라서 입력으로 그래프를 생성하고(이때 그래프는 i번 노드에 연결된 노드를 모두 저장한다.),

DFS를 이용하여 1번에서 연결된 노드를 방문 표시해준다.

마지막으로 방문 표시한 개수를 세는데, 본인 노드(1번 노드)는 카운트하지 않으므로 2번 노드부터 끝까지 방문 표시된 노드 개수를 센다.

"이것이 코딩테스트다" 책 문제 _ DFS/BFS 문제

문제)

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

입력조건

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

출력조건

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

풀이)

이 문제는 BFS 문제로 해결했다! (1, 1)에서 시작하여 주변을 탐색하며 1이 있는 부분을 택해서 가기 때문에 모든 노드를 탐색하므로 BFS가 편리하다고 생각했다. 사실 BFS로 해결을 하는 부분까진 감을 잡았는데 최소 이동 칸의 개수를 세는 방법을 잘 캐치를 못했다.

코드는 다음과 같다.

from collections import deque
N, M = map(int, input().split())
maze = []
for i in range(N):
    maze.append(list(map(int, input())))

# 첫 번째 칸 무조건 포함
count = 1
# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#bfs
def bfs(x, y):
    que = deque()
    que.append((x, y))
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if maze[nx][ny] == 0:
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                que.append((nx, ny))
    return maze[N-1][M-1]


print(bfs(0, 0))
print(maze)


# 결과: 10
# maze
# [[3, 0, 5, 0, 7, 0], 
#  [2, 3, 4, 5, 6, 7], 
#  [0, 0, 0, 0, 0, 8], 
#  [14, 13, 12, 11, 10, 9], 
#  [15, 14, 13, 12, 11, 10]]

노드를 방문했을때 길이 존재한다면 '이전 노드 값 + 1'을 저장한다!

맨 마지막 노드까지 bfs를 진행한다면 맨 마지막 노드에는 전체 거리 값이 저장된다.

다만 여기에서 maze 전체를 출력해본 값을 본다면 알 수 있듯이 시작 위치가 1이 아닌 3으로 변경된다.

왜냐하면 코드 상에서는 첫 번째 노드를 다시 방문할 수 있게 되어있기 때문이다!!

하지만 문제를 푸는 데에는 이상이 없기 때문에 참고 사항으로 알아두면 좋을 것 같다.

"이것이 코딩테스트다" 책 문제 _ DFS/BFS 문제

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

예시) 4x5 얼음틀 : 아이스크림 3개 생성

입력조건

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

출력조건

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

풀이)

이 문제는 DFS로 풀어보았다! 전형적인 문제가 아닐까 생각한다.

N, M = map(int, input().split())
ice = []
for i in range(N):
    ice.append(list(map(int, input())))


def dfs(x, y):
    global N, M
    if x < 0 or x >= N or y < 0 or y >= M:
        return False
    if ice[x][y] == 0:
        ice[x][y] = 1
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

count = 0
for i in range(N):
    for j in range(M):
        if dfs(i, j) == True:
            count += 1

print(count)

얼음판 ice 구조를 이중 list로 저장해주고, (0, 0)부터 차례로 순회한다.

순회할때는 좌표 범위를 확인하고 0일경우 1로 바꿔준다.

dfs를 실행중인 좌표 기준으로 좌, 우, 상, 하를 똑같이 dfs로 순회한다.

return 값이 True로 끝나면 순회 완료! False 일 경우는 범위를 넘었거나 1인 경우이다.

또한 BFS로도 풀어보았다!!! (책은 DFS에 해당하는 풀이만 나와있다.)

from collections import deque

N, M = map(int, input().split())
ice = []
for i in range(N):
    ice.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(i, j):
    queue = deque()
    if ice[i][j] == 0:
        queue.append([i, j])
        while queue:
            x, y = queue.popleft()
            for p in range(4):
                nx = x + dx[p]
                ny = y + dy[p]
                if 0 <= nx < N and 0 <= ny < M:
                    if ice[nx][ny] == 0:
                        ice[nx][ny] = 1
                        queue.append([nx,ny])
                    else:
                        continue
                else:
                    continue
        return 1
    else:
        return 0



count = 0
for i in range(N):
    for j in range(M):
        count += bfs(i, j)
print(count)

좌, 우, 상, 하 이동을 dx, dy를 생성하여 만들었다. dfs와 같이 순회는 (0, 0) 부터 시작한다.

Ice가 0일 경우만 queue에 삽입 후 bfs를 진행하고, 아닐 경우는 없는 경우로 판단해 return 0한다.

다음 좌표의 ice가 0일 경우 1로 바꾸고 queue에 삽입한다. 이것을 queue가 다 끝날때까지 반복!

queue가 다 끝나면 해당 좌표의 bfs가 끝난 것이므로 1을 return해준다.

그리고 bfs 개수를 모두 더해주면 끝!!

DFS(Depth-First Search, 깊이 우선 탐색)

그래프에서 깊은 부분을 우선적을 탐색하는 알고리즘. 스택(stack)을 사용한다!

동작 과정:

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

2번 과정에서 방문하지 않은 인접 노드를 스택에 넣을 때 순서는 상관없지만, 문제에 따라서 알파벳 순서 또는 작은 숫자 순서대로 가는 경우가 많으므로 작은 노드 순서대로 넣는 경우가 많다.

그럼 실습해보자!!

def dfs(graph, v, visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# DFS 호출
dfs(graph, 1, visited)


### 출력 결과(stack에 들어간 순서대로): 1 2 5 6 7 3 4

BFS(Breath-First Search, 너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘. 큐(queue)를 사용한다!

동작 과정:

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS와 마찬가지로 작은 노드부터 수행하는 경우가 많다!

위에 있는 그래프를 이용하여 다시 실습해보자!

from collections import deque

# BFS 정의
def bfs(graph, start, visited):
    # queue 구현 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = ' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# BFS 호출
bfs(graph, 1, visited)


### 출력 결과(큐에 삽입된 순서대로): 1 2 3 5 4 6 7