백준 문제들
from collections import deque
def dfs(li,V,visited):
#현재 노드 방문 처리
visited[V] = 1
print(V, end = ' ')
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in li[V]:
if visited[i] == 0:
dfs(li,i,visited)
def bfs(li,V,visited):
deq = deque([V])
visited[V] = 0
while deq: # 큐가 빌때 까지
#맨 처음 인자 빼고, 출력
V = deq.popleft()
print(V, end = ' ')
#방문하지 않은 인자 큐에 추가
for i in li[V]:
if visited[i] == 1:
deq.append(i)
visited[i] = 0
N, M, V = map(int, input().split())
li = [[]for i in range(N+1)]
for i in range(M):
num_1, num_2 = map(int, input().split())
li[num_1].append(num_2)
li[num_2].append(num_1)
visited = [0] * (N + 1)
#리스트 정렬
for i in range(1,N+1):
li[i].sort()
dfs(li, V, visited)
print()
bfs(li, V, visited)
from collections import deque
t = int(input())
def bfs(i,j,li,visited):
global n, m
if li[i][j] == 0 or visited[i][j] == True:
return 0
else:
q = deque()
q.append([i,j])
visited[i][j] = True
x = [1,-1,0,0,]
y = [0,0,1,-1]
while q:
a,b = q.popleft()
visited[a][b] = True
for k in range(4):
if 0 <= a+x[k] < n and 0 <= b+y[k] < m :
if li[a+x[k]][b+y[k]] == 1 and visited[a+x[k]][b+y[k]] == False:
q.append([a+x[k],b+y[k]])
visited[a+x[k]][b+y[k]] = True
return 1
for i in range(t):
m , n , k = map(int,input().split())
li = [ [0 for _ in range(m)] for i in range(n) ]
count = 0
for i in range(k):
x, y = map(int, input().split())
li[y][x] = 1
visited = [ [False for _ in range(m)] for i in range(n) ]
for i in range(n):
for j in range(m):
count += bfs(i,j,li,visited)
print(count)
from collections import deque
answer = 0
r,c = map(int,input().split())
li = []
for i in range(r):
li.append(list(input()))
alp = [False] * 26
# A= 97
x = [1,-1,0,0]
y = [0,0,-1,1]
result = []
def bfs(i,j):
global r,c,answer
count = 0
q = deque()
q.append([i,j])
temp = li[i][j]
alp[90-ord(temp)] = True
li[i][j] = 0
while q:
a,b = q.popleft()
for k in range(4):
nx = a + x[k]
ny = b + y[k]
if 0<= nx < r and 0<= ny < c and li[nx][ny] !=0:
temp = li[nx][ny]
if alp[90-ord(temp)] == False:
q.append([nx,ny])
li[nx][ny] = 0
alp[90-ord(temp)] = True
answer += 1
return answer
for i in range(r):
for j in range(c):
if li[i][j] != 0 :
result.append(bfs(i,j))
print(max(result))from collections import deque
n , m = map(int, input().split())
maze = []
for _ in range(n):
maze.append(list(map(int,input())))
answer = 0
def bfs(maze,i,j):
global n,m
q = deque()
q.append((i,j))
maze[i][j] = 0
x = [1,-1,0,0]
y = [0,0,-1,1]
while q:
a,b = q.popleft()
for k in range(4):
nx = a+x[k]
ny = b+y[k]
if 0> nx or n<= nx or 0>ny or m <=ny:
continue
if maze[nx][ny] == 1:
q.append((nx,ny))
maze[nx][ny] = maze[a][b] + 1
return maze[n-1][m-1]
answer = bfs(maze,0,0)
print(answer + 1)def dfs(li,v,visited):
visited[v] = True
global count
for i in li[v]:
if not visited[i]:
dfs(li,i,visited)
count += 1
return count
c = int(input())
n = int(input())
li = [[] for i in range(c+1)]
for i in range(1, n+1):
num_1,num_2 = map(int, input().split())
li[num_1].append(num_2)
li[num_2].append(num_1)
count = 0
visited = [False] * (c + 1)
print(dfs(li,1,visited))from collections import deque
n = int(input())
estate = []
for i in range(n):
estate.append(list(map(int,input())))
house_n = []
def bfs(estate, i,j):
global n
house = 1
q = deque()
q.append((i,j))
estate[i][j] = 0
x = [1,-1,0,0]
y = [0,0,-1,1]
while q:
a, b = q.popleft()
for k in range(4):
nx = a + x[k]
ny = b + y[k]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if estate[nx][ny] == 1:
estate[nx][ny] = 0
q.append((nx, ny))
house += 1
return house
for i in range(n):
for j in range(n):
if estate[i][j] == 1 :
house_n.append(bfs(estate, i,j))
house_n.sort()
print(len(house_n))
for i in house_n:
print(i)from collections import deque
def bfs(i,j,li,visited):
global w,h
if li[i][j] == 0 or visited[i][j] == True:
return 0
else :
q = deque()
q.append([i,j])
x = [1,-1,0,0,-1,1,-1,1]
y = [0,0,-1,1,1,1,-1,-1]
visited[i][j] = True
while q:
a, b = q.popleft()
visited[a][b] = True
for k in range(8):
if a + x[k] < 0 or b + y[k] < 0 or a + x[k] >= h or b + y[k] >= w:
continue
else:
if li[a + x[k]][b + y[k]] == 1 and visited[a + x[k]][b + y[k]] == False:
visited[a + x[k]][b + y[k]] = True
q.append([a + x[k], b + y[k]])
return 1
while(1):
w,h = map(int, input().split())
if w == 0 and h==0:
break
li = [list(map(int, input().split())) for i in range(h)]
visited = [[False for i in range(w)] for j in range(h)]
answer = 0
for i in range(h):
for j in range(w):
answer += bfs(i,j,li,visited)
print(answer)from collections import deque
m,n = map(int,input().split())
box = []
li = []
for i in range(n):
box.append(list(map(int,input().split())))
for j in range(m):
if box[i][j] == 1:
li.append([i,j])
x = [1,-1,0,0]
y = [0,0,-1,1]
q = deque()
nice_to = len(li)
for i,j in li:
q.append([i,j])
while q:
a,b = q.popleft()
for k in range(4):
nx = a + x[k]
ny = b + y[k]
if 0<= nx < n and 0<= ny < m:
if box[nx][ny] == 0:
q.append([nx,ny])
if box[nx][ny] != -1:
box[nx][ny] = box[a][b] + 1
for i in range(n):
for j in range(m):
if box[i][j] ==0:
print(-1)
exit()
if box[a][b] == 1:
print(0)
else:
print(box[a][b]-1)
from collections import deque
n = int(input())
painting = []
normal = 0
rg = 0
visited = [[False for i in range(n)] for j in range(n)]
x = [1,-1,0,0]
y = [0,0,-1,1]
for i in range(n):
painting.append(list(input()))
def bfs(li,i,j,visited):
global n
q = deque()
q.append([i,j])
visited[i][j] == True # 방문했으면
while q:
a,b = q.popleft()
for k in range(4):
nx = a + x[k]
ny = b + y[k]
if 0<= nx <n and 0<= ny < n :
if visited[nx][ny] != True and li[nx][ny] == li[i][j]:
q.append([nx,ny])
visited[nx][ny] = True
return 1
# 적록색맹 아닌 사람이 보는 구역의 개수2
for i in range(n):
for j in range(n):
if visited[i][j] == False:
normal += bfs(painting, i,j,visited)
#적록 색맹이 보는 그림 리 페인팅
for i in range(n):
for j in range(n):
visited[i][j] = False
if painting[i][j] == 'R':
painting[i][j] = 'G'
# 적록생맹이 보는 구역의 개수
for i in range(n):
for j in range(n):
if visited[i][j] == False:
rg += bfs(painting,i,j,visited)
print(normal,rg)
인생 살자.