230307 - BFS/DFS

[robert-min]

문제

1. boj10026 - 적록색약 링크
2. boj2206 - 벽 부수고 이동하기 링크
3. boj2644 - 촌수 계산 링크
4. boj20304 - 비밀번호 제작 링크
5. boj7569 - 토마토 링크

[robert-min]

boj10026 - 적록색약

• dfs 풀이 때, 런타임 에러 발생 시 set.setrecursionlimit 에러 확인

"""
Return : 적록색약, 일반사람 구역의 수
- 적록색약은 빨강R 초록G 같은 구역으로 봄
"""
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N = int(input())
matrix = []
for _ in range(N):
    matrix.append(list(input()))

# 일반
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, color):
    if matrix[x][y] == color:
        visited[x][y] = 1
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N or ny >= N: continue
            if visited[nx][ny]: continue
            dfs(nx, ny, color)

cnt = 0
visited = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            dfs(i, j, matrix[i][j])
            cnt += 1

# 적록 색약
cnt_c = 0
visited = [[0] * N for _ in range(N)]
def dfs_rg(x, y):
    if matrix[x][y] in ["R", "G"]:
        visited[x][y] = 1
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N or ny >= N: continue
            if visited[nx][ny]: continue
            dfs_rg(nx, ny)

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            if matrix[i][j] == "B":
                dfs(i, j, "B")
            else:
                dfs_rg(i, j)
            cnt_c += 1

print(cnt, end=" ")
print(cnt_c)

[robert-min]

boj2206 - 벽 부수고 이동하기

• 완전 탐색을 풀 경우 시간초과
• 벽을 부순 경우와 그렇지 않은 경우를 한 번의 탐색 때 확인하도록 수정

"""
Return : (N,M) 칸으로 가는 최단 경로
- 벽을 1개 부술 수 있음
- 불가능할 때, -1 출력

- 입력 받을 때 벽(1) 위치 입력
- 벽 없애는 모든 경우 탐색
- 이동 여부 확인(bfs)
"""
import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for _ in range(n):
    row = list(str(input().rstrip()))
    graph.append(list(map(int, row)))

# 3차원 배열 사용 -> visited[x][y][z], z = 0 or 1로 기록
# z = 0이면 벽을 뚫지 않고 간 경우, z = 1이면 벽을 뚫고 간 경우
moves = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
]
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

def bfs():
    q = deque()
    q.append([0, 0, 0])
    visited[0][0][0] = 1

    while q:
        x, y, w = q.popleft()

        # 목표지점 도달 시 해당 위치까지의 거리 리턴
        if x == n - 1 and y == m - 1:
            return visited[x][y][w]

        for move in moves:
            nx, ny = x + move[0], y + move[1]

            if 0 <= nx < n and 0 <= ny < m:
                # 현재 위치로 이동할 수 있고, 아직 방문하지 않았다면
                if graph[nx][ny] == 0 and visited[nx][ny][w] == 0:
                    visited[nx][ny][w] = visited[x][y][w] + 1
                    q.append([nx, ny, w])

                # 현재 위치가 벽이고, 벽을 아직 부수지 않았다면
                elif graph[nx][ny] == 1 and w == 0:
                    visited[nx][ny][w + 1] = visited[x][y][w] + 1
                    q.append([nx, ny, w + 1])

    # 목표지점까지 도달하지 못한다면 -1 리턴
    return -1

print(bfs())

[robert-min]

boj2644 - 촌수 계산

"""
Return : 두 사람의 촌수 계산
- 촌 수를 계산할 수 없을 때 -1

x, y : y가 부모
- graph로 연결관계를 표현하고 도착 노드까지 갈 수 있는지 확인
- 노드 이동하면서 cnt += 1
- 이동 못하면 -1
"""
import sys
input = sys.stdin.readline
N = int(input())
start, end = map(int, input().split())

M = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# start - end 확인
visited = [0] * (N+1)
from collections import deque

def bfs(start):
    Q = deque([start])
    visited[start] = 1
    while Q:
        now = Q.popleft()
        for nx in graph[now]:
            if not visited[nx]:
                visited[nx] = visited[now] + 1
                Q.append(nx)

bfs(start)
print(visited[end]-1)

[robert-min]

boj20304 - 비밀번호 제작

import sys
from collections import deque

input=sys.stdin.readline

n=int(input())
m=int(input())
p=list(map(int,input().split()))
safety=[21 for _ in range(n+1)]
dq=deque()

for i in p: 
    safety[i]=0
    dq.append(i)

ans=0

while len(dq)!=0:
    cur=dq.popleft()

    for i in range(20):
        x = (1<<i) ^ cur
        if x<=n and safety[cur]+1<safety[x]:
            safety[x]=safety[cur]+1
            ans=max(safety[x],ans)
            dq.append(x)
print(ans)

[robert-min]

boj7569 - 토마토

• 3차원 bfs 탐색

"""
Return : 토마토가 다 익으려면 최소 며칠이 걸리는지 출력
- 저장될 때부터 모두 익어 있으면 0, 모두 익지 못하면 -1
- 익은 1, 익지 않은 0, 없는 -1

[[]] x, y
[[[]]] z, x, y
이동 dx, dy, dz(위, 아래)
- 입력 받을 때, == 0 토마토 수 계산
- 토마토 수가 0이 아니면 -1
"""
import sys
input = sys.stdin.readline
M, N, H = map(int, input().split())

graph = [[] for _ in range(H)]
start = []
cnt = 0
for i in range(N * H):
    temp = list(map(int, input().split()))
    for idx, v in enumerate(temp):
        if v == 1:
            start.append((i//N, i % N, idx))
        elif v == 0:
            cnt += 1
    graph[i // N].append(temp)

# print(start)
# print(graph)
# print(cnt)

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

day = -1
from collections import deque
def bfs(start):
    global cnt, day
    while start:
        Q = deque(start)
        day += 1
        start = []
        while Q:
            z, x, y = Q.popleft()
            for k in range(6):
                nz = z + dz[k]
                nx = x + dx[k]
                ny = y + dy[k]
                if nz < 0 or nz >= H: continue
                if nx < 0 or nx >= N: continue
                if ny < 0 or ny >= M: continue
                if graph[nz][nx][ny] == 0:
                    cnt -= 1
                    graph[nz][nx][ny] = 1
                    start.append((nz, nx, ny))

if cnt == 0:
    print(0)
else:
    bfs(start)
    if cnt == 0:
        print(day)
    else:
        print(-1)