[백준] 1707, 2667, 2178, 7576

이분 그래프 (1707번)

• 사이트/난이도: 백준 / 골드4
• 코드

# 골드4 이분 그래프
import sys
from collections import deque
input = sys.stdin.readline

def bfs(start):
    global flag
    q = deque([])
    q.append(start)
    if visited[start] == 0:
        visited[start] = 1
    
    while q:
        now = q.popleft()
        for i in graph[now]:
            if visited[i] == 0:
                if visited[now] == 1:
                    visited[i] = 2
                else:
                    visited[i] = 1
                q.append(i)
            else:
                if visited[now] == visited[i]:
                    flag = False
                    return

k = int(input())
for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visited = [0] * (v+1)
    flag = True
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    for i in range(1, v+1):
        bfs(i)
    
    if flag:
        print("YES")
    else:
        print("NO")

• 느낀점
  • 처음에 이분 그래프가 먼지 이해가 안갔다. 그래프의 정점을 두개로 칠할 때, 인접한 정점끼리 다른 색을 가지는 그래프라고 이해하니 편했다. (아래 블로그 그림을 통해 아이디어를 얻었다.)
  • https://hongcoding.tistory.com/20
  • 그 후, visited 상태를 3개로 방문안함, 색1, 색2 처리로하여 푸니 간단하게 풀렸다.

단지번호붙이기 (2667번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 단지번호붙이기
from collections import deque

n = int(input())
graph = []
visited = [[False] * n for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(n):
    graph.append(list(map(int, input())))

def bfs(x, y):
    global count
    if visited[x][y] or graph[x][y] == 0:
        return
    q = deque([])
    q.append((x,y))
    visited[x][y] = True
    count = 1
    while q:
        x, y = q.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 >= n:
                continue
            if visited[nx][ny]:
                continue
            if graph[nx][ny] == 0:
                continue

            visited[nx][ny] = True
            count += 1
            q.append((nx, ny))

answer = []
for i in range(n):
    for j in range(n):
        count = 0
        if graph[i][j] != 0:
            bfs(i, j)
        if count != 0:
            answer.append(count)
answer.sort()
print(len(answer))
for a in answer:
    print(a)

• 느낀점
  • 그냥 간단한 bfs 문제
  • input값으로 공백으로 주지않고 11111 이런식으로 붙여서 주면 input().split() 이 아니라 input() 으로 받고 input = sys.stdin.readline 을 안해줘야지 정상적으로 배열에 담김. (이거때문에 헤멤 ㅋㅋ)

미로 탐색 (2178번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 미로 탐색
from collections import deque

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

def bfs(x, y):
    q = deque([])
    q.append((x,y))

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

    while q:
        x, y = q.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 graph[nx][ny] == 1:
                graph[nx][ny] += graph[x][y]
                q.append((nx,ny))

bfs(0,0)
print(graph[n-1][m-1])

• 느낀점
  • 길이가 1인 최단거리 문제는 bfs 로 풀면 매우 간단하게 풀린다.
  • bfs를 하면서 안 간 거리를 1로 생각해서 계속 업데이트 해주면 된다.

토마토 (7576번)

• 사이트/난이도: 백준 / 골드5
• 코드

# 골드5 토마토
import sys
from collections import deque
input = sys.stdin.readline

m, n = map(int, input().split())
graph = []
answer = 0
for _ in range(n):
    graph.append(list(map(int, input().split())))

def bfs():
    global answer
    q = deque([])
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                q.append((i, j, 0))
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while q:
        x, y, time = q.popleft()
        answer = max(answer, time)
        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 graph[nx][ny] == 0:
                graph[nx][ny] = 1
                q.append((nx, ny, time+1))

bfs()
flag = True
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            flag = False
            break

print(answer) if flag else print(-1)

• 느낀점
  • 문제에서 모든 토마토가 익는 최소일수 라고 언급했기 때문에 최단거리 문제랑 비슷하므로 bfs 이용한다.
  • 일단 익은 토마토를 큐에 다 넣고 익은 시간은 x,y 좌표 옆에 time이라는 변수로 계속 올려줬다.