[백준] 1080, 1697 (파이썬)

오늘은 그리디문제와 DFS,BFS 문제를 둘 다 풀이했다. 다시 원하던 대로의 루틴으로 돌아온 것 같아서 개인적으로 기분이 좋았다. 루틴을 이대로만 유지하는 것이 현재로썬 목표이다.

백준 1080번 행렬

# 문제를 이해하기 어려웠던 문제, 알고리즘을 찾아보니 내용은 생각보다 간단했다.
import sys
N,M = map(int,sys.stdin.readline().split())
A_list,B_list = [],[]
for _ in range(N):
    A_list.append(list(map(int,sys.stdin.readline().strip())))
for _ in range(N):
    B_list.append(list(map(int,sys.stdin.readline().strip())))
count = 0
# 변환함수
def convert(x, y):
    for row in range(x, x + 3):
        for col in range(y, y + 3):
            A_list[row][col] = 1 - A_list[row][col]        
# 가능한 행렬개수
for i in range(N - 2):
    for j in range(M - 2):
        if A_list[i][j] != B_list[i][j]:
            convert(i, j)
            count += 1
# A,B 일치여부 확인  
while True:
    for i in range(N):
        for j in range(M):
            if A_list[i][j] != B_list[i][j]:
                print(-1)
                exit(0)
    print(count)
    exit(0)

백준 1697번 숨바꼭질

# 처음에 BFS라고 생각하지 않았다. 이런유형도 BFS임을 명심하자
import sys
from collections import deque
def bfs():
    queue = deque()
    queue.append(N)
    while queue:
        spot = queue.popleft()
        if spot==K:
            print(num[spot])
            break
        for i in (spot-1,spot+1,spot*2):
            if 0<=i<=100000 and num[i] == 0:
                num[i] = num[spot] + 1
                queue.append(i)
N,K = map(int,sys.stdin.readline().split())
num = [0] * (100001)
bfs()