1-1.py

import sys
sys.setrecursionlimit(10**6)

class Location:
    def __init__(self, row=0, col=0):
        self.row = row
        self.col = col

m, n = map(int, input().split())
map_example = [[0 for _ in range(n)] for _ in range(m)]
visited = [[False for _ in range(n)] for _ in range(m)]

for i in range(m):
    a = input()
    map_example[i] = list(map(int, list(str(a))))

# map: 미로 정보를 저장하는 2차원 배열
# m, n: 미로의 열과 크기
# start, dest: 출발지와 목적지
# visited: 미로의 행과 열의 각 위치가 방문되었는지 아닌지를 확인하기 위한 2차원 배열
# 갈 수 있는 곳을 1로, 없는 곳을 0으로 만들어보자.
def findPath(map, m, n, start, dest, visited):
    next = Location()
    if map[start.row][start.col] == 1:  # 시작점이 1이라면
        visited[start.row][start.col] = True # visited=True, 그러니까 방문을 했다고 표시하는 것
    else: # 그게 아니면 -1을 리턴하고 함수 종료
        return False
    # print("(",start.row,",",start.col,")") # 현재 위치 출력
    if start.row == dest.row: # 현재 위치가 목적지와 같다면 1 리턴하고 함수 종료
        return True
    if start.col < n-1: # 오른쪽으로 이동하는 경우
        if map[start.row][start.col+1] == 1 and not visited[start.row][start.col+1]:
            # 현재 지점에서 오른쪽으로 한 칸 옆의 값이 1이고 방문하지 않았다면,
            next.row = start.row  # row는 그대로
            next.col = start.col + 1  # col은 +1
            if findPath(map, m, n, next, dest, visited):  # findPath 함수를 실행할 수 있다면
                return True  # 1 리턴하고 함수 종료
    if start.row < m-1:  # 아래쪽
        if map[start.row+1][start.col] == 1 and not visited[start.row+1][start.col]:
            next.row = start.row + 1
            next.col = start.col
            if findPath(map, m, n, next, dest, visited):
                return True
    if start.col > 0: # 왼쪽
        if map[start.row][start.col-1] == 1 and not visited[start.row][start.col-1]:
            next.row = start.row
            next.col = start.col - 1
            if findPath(map, m, n, next, dest, visited):
                return True
    if start.row > 0: # 위쪽
        if map[start.row-1][start.col] == 1 and not visited[start.row-1][start.col]:
            next.row = start.row - 1
            next.col = start.col
            if findPath(map, m, n, next, dest, visited):
                return True
    return False # 4가지 전부 이동할 수 없는 경우, False 리턴

# print(findPath(map_example, m, n, Location(1, 0), Location(5, 6), visited))

for i in range(n):
    result = findPath(map_example, m, n, Location(0, i), Location(m-1, None), visited)
    if result:
        break

if result:
    print(1)
else:
    print(-1)



# for i in range(n):
#     start = Location(0, i)  # row 개수만큼 start 바꿔가며 길 찾기
#     # print(start.row, start.col)
#     result = findPath(map_, m, n, start, dest, visited)
#     if result == True:      # 만약 마지막 행에 도달했다면, 반복문 종료
#         break
# 우선 1을 통로로 하는 경로 찾기 여부는 완료를 했는데, 이제 문제는 .. start값과 dest값을 지정해 줘야 된다는 것이다.

# '맨윗줄에서 맨아랫줄을 갈 수 있냐' 가 중요한 것이다.
# 맨 윗줄을 우선 열 n에 대한 for문(i)으로 돌면서 1인 경우:
#   이제 행 m에 대한 for문(j)을 돈다.
#       미로를 리스트화한 map_example에서, 마지막 줄의 j번째 값이 1이라면:
#           findPath가 True일 경우, 그러니까 map_example[0][i]에서 map_example[m-1][j]로 가는 길이 있는경우
#               1을 출력한다. (갈 수 있다는 뜻)
#           가는 길이 없는 경우는, i를 더하고 다시 해본다.
#       마지막 줄의 j번째 인덱스가 1이 아니라면 1을 더해준다.
#
# 6 10
# 0110000011
# 1101111101
# 1101010111
# 1111010111
# 0100111000
# 1011110111

# 7 12
# 000000000000
# 111011011110
# 010010010010
# 011111011010
# 000010000010
# 011111111111
# 000000000000

1-2.py

from collections import deque

m, n = map(int, input().split())
map_example = [[0 for _ in range(n)] for _ in range(m)]
distance = [[0 for _ in range(n)] for _ in range(m)]

for i in range(m):
    a = input()
    map_example[i] = list(map(int, list(str(a))))
queue = deque()

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

def bfs(map, start_y, start_x):
    visited = [[False for _ in range(n)] for _ in range(m)]
    queue.append([start_x, start_y])
    distance[start_y][start_x] = 1
    while queue:
        x, y = queue.popleft()    # row와 col에 map_example[0][i]를 넣음
        for i in range(4):
            # 0일땐 서쪽, 1일땐 북쪽, 2일땐 동쪽, 3일땐 남쪽
            new_x = x + dx[i]
            new_y = y + dy[i]
            if 0 <= new_x < n and 0 <= new_y < m and not visited[new_y][new_x]:
                if map[new_y][new_x] == 1:
                    visited[new_y][new_x] = True # 1
                    queue.append((new_x, new_y))
                    distance[new_y][new_x] = distance[y][x] + 1 # 2
                    if new_y == m-1:
                        a = distance[new_y][new_x]
                        queue.clear()
                        return a

new_list = []
for i in range(n):
    if map_example[0][i] == 1:
        new_list.append(bfs(map_example, 0, i))
res = list(filter(None, new_list))
if len(res) == 0:
    print(-1)
else:
    print(min(res))
# 6 10
# 0110000011
# 1101111101
# 1101010111
# 1111010111
# 0100111000
# 1011110111

2.py

import sys

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

adj = [[] for _ in range(n)]

for _ in range(m):
    src, dest = map(int, sys.stdin.readline().split())
    adj[src].append(dest)
    adj[dest].append(src)

# print(adj)
# 현재 adj는 이중 리스트 형태로 인접 리스트를 구현한 상태

def dfs(v, visited):
    people = 0
    stack = [v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            people += 1
            for w in adj[v]:
                stack.append(w)
    return visited, people

visited = []
relationship = 0
result = []
for i in range(n):
    visited, people = dfs(i, visited)
    if people != 0:
        relationship += 1
        result.append(people)
print(relationship)
print(max(result), min(result))

3-1.py

from collections import deque

queue = deque()
n, m = list(map(int, input().split()))

adj = [[] for _ in range(n)]
for _ in range(m):
    src, dest = map(int, input().split())
    adj[src].append(dest)
    adj[dest].append(src)

start_station, final_station = map(int, input().split())


def bfs(start, destination, visited):
    distance = [0] * n
    queue.append(start)
    visited[start] = True
    while queue:
        start = queue.popleft()
        for w in adj[start]:
            if destination in adj[start]:
                w = destination
            if not visited[w]:
                visited[w] = True
                queue.append(w)
                distance[w] = distance[start] + 1
                if w == destination:
                    queue.clear()
                    return distance[w]
    return -1


visited = [False] * n
print(bfs(start_station, final_station, visited))