Baekjoon 22352
in Study / Computer science on Baekjoon 22352
BFS
Description
VUNO는 빅데이터와 딥러닝 기술을 통해 학습한 인공지능을 이용해 의학 전문가들의 판단에 도움을 주는 Medical AI 솔루션을 개발하는 전문 기업이다.
VUNO는 최근 SP라는 강력한 새로운 촬영 기법을 개발했다. 이 기법을 사용하면 인체 조직이 격자 형태로 표현되고, 격자의 각 칸에는 해당 부분의 각종 분석 결과를 압축한 하나의 데이터 값이 부여된다. VUNO는 이 SP 촬영 기법을 사용해 CPCU-1202라는 새로운 항체를 연구하려고 한다.
조직에 CPCU-1202 백신을 놓으면, 격자의 칸 중 하나에 항체가 생성된다. 이 항체는 현재 속해 있는 칸과 같은 데이터 값을 가지면서 상하좌우로 인접한 칸 (same value)이 있을 경우 그 칸으로 퍼져나간다. 이 과정을 계속 반복하다가 항체가 더 이상 퍼져나갈 수 없게 되면, 항체는 조직에 완전히 스며든다. 그 결과로, 항체가 퍼졌던 칸들의 데이터 값은 모두 어떤 동일한 값으로 새로 업데이트된다. 이때, 우연히 원래의 데이터 값과 업데이트된 데이터 값이 동일할 수도 있다.
VUNO의 연구 데이터는 하나의 조직에 백신을 놓기 전의 촬영 결과와 백신을 놓은 뒤의 촬영 결과가 한 쌍으로 이루어져 있다. 두 장의 촬영 결과가 주어질 때, 이 조직에 놓은 백신이 CPCU-1202 백신일 가능성이 있는지 판단하는 프로그램을 작성하라.
Input
첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 N과 M이 주어진다. (1 <= N, M <= 30) 이는 촬영 결과가 세로로 N칸, 가로로 M칸 크기의 격자라는 것을 의미한다.
다음 N개의 줄에는 백신을 놓기 전의 촬영 결과가 주어진다. 각 줄에는 1 이상 1000 이하의 정수 M개가 공백으로 구분되어 주어지며, i번째 줄의 j번째 수는 촬영 결과의 i번째 행 j번째 칸의 데이터 값을 의미한다.
다음 N개의 줄에는 백신을 놓은 뒤의 촬영 결과가 위와 동일한 형식으로 주어진다.
Output
촬영 대상이 맞은 백신이 CPCU-1202 백신일 수 있다면 YES, 그럴 수 없다면 NO 를 출력하라.
Example I & O
Input 1
4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
4 4 4 1
4 4 1 3
4 1 3 3
1 3 3 3
Output 1
YES
Input 2
4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
Output 2
YES
Input 3
4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 2 3
2 1 3 3
1 3 3 3
Output 3
YES
Input 4
4 4
2 2 2 1
2 2 1 2
2 1 2 2
1 2 2 2
3 3 3 1
3 3 1 3
3 1 3 3
1 3 3 3
Output 4
NO
Input 5
3 5
1 1 1 3 3
1 1 2 3 3
1 1 2 2 4
1 1 1 4 4
1 1 2 4 4
1 1 2 2 4
Output 5
YES
Input 6
4 4
2 2 2 4
2 2 4 4
2 6 6 3
6 6 3 3
2 2 2 4
2 2 4 4
2 3 2 3
3 3 3 3
Output 6
NO
My solution
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
N, M = map(int, input().split())
def BFS(graph1, graph2, start_x, start_y):
copyGraph1 = [l1[:] for l1 in graph1]
copyGraph2 = [l2[:] for l2 in graph2]
visited = deque()
need_visit = deque()
need_visit.append((start_x, start_y))
d = copyGraph2[start_y][start_x]
while need_visit:
x, y = need_visit.popleft()
visited.append((x, y))
data = copyGraph1[y][x]
copyGraph1[y][x] = 0
if copyGraph2[y][x] == d:
copyGraph2[y][x] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= M or nx < 0 or ny >= N or ny < 0:
continue
if (nx, ny) not in visited and copyGraph1[ny][nx] == data:
need_visit.append((nx, ny))
if copyGraph1 == copyGraph2:
return 1, visited
else:
return 0, visited
preGraph = [[0] * M for i in range(N)]
postGraph = [[0] * M for i in range(N)]
for i in range(N):
a = input().split()
for j in range(len(a)):
preGraph[i][j] = int(a[j])
for i in range(N):
a = input().split()
for j in range(len(a)):
postGraph[i][j] = int(a[j])
completeVisited = []
flag = False
for i in range(N):
for j in range(M):
if (j, i) in completeVisited:
continue
antibody, v = BFS(preGraph, postGraph, j, i)
completeVisited.extend(v)
if antibody == 1:
flag = True
break
else:
flag = False
if flag:
print("YES")
break
if not flag:
print("NO")
Sketch
Code Analysis
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
N, M = map(int, input().split())
dx & dy pair : for movement toward adjacent nodes
N : number of rows
M : number of columns
def BFS(graph1, graph2, start_x, start_y):
copyGraph1 = [l1[:] for l1 in graph1]
copyGraph2 = [l2[:] for l2 in graph2]
visited = deque()
need_visit = deque()
need_visit.append((start_x, start_y))
d = copyGraph2[start_y][start_x]
graph1 : preGraph
graph2 : postGraph
start_x : x coordinate of start point for BFS search
start_y : y coordinate of start point for BFS search
copyGraph : deep copy version of graph for using and modifying only in BFS function (original graph is not changed)
deep copy : module < slicing in terms of efficiency
visited, need_visit : BFS components
node : tuple format (representing coordinate)
d : for the condition (orange color in Sketch)
while need_visit:
x, y = need_visit.popleft()
visited.append((x, y))
data = copyGraph1[y][x]
copyGraph1[y][x] = 0
if copyGraph2[y][x] == d:
copyGraph2[y][x] = 0
BFS search target == preGraph (not postGraph)
Searched point : change to 0 for comparing between preGraph (copy) and postGraph (copy) → because BFS search region (orange region in sketch) should have same value in both graph for using == (in order to only compare the rest region)
data : criteria for adjacency nodes
if : for the condition in sketch (have 0 value only in the case of same value)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= M or nx < 0 or ny >= N or ny < 0:
continue
if (nx, ny) not in visited and copyGraph1[ny][nx] == data:
need_visit.append((nx, ny))
Basic BFS components
if copyGraph1 == copyGraph2:
return 1, visited
else:
return 0, visited
Consequently, == means that we only compare the rest region between preGraph (copy) and postGraph (copy), but (rest1 == rest2) AND (copyGraph1 != copyGraph2) can be true in the case of violating the condition (orange color in Sketch)
if both graph are same : There can be the antibody
if both graph are not same : There cannot be the antibody
preGraph = [[0] * M for i in range(N)]
postGraph = [[0] * M for i in range(N)]
for i in range(N):
a = input().split()
for j in range(len(a)):
preGraph[i][j] = int(a[j])
for i in range(N):
a = input().split()
for j in range(len(a)):
postGraph[i][j] = int(a[j])
formation of preGraph and postGraph
completeVisited = []
flag = False
for i in range(N):
for j in range(M):
if (j, i) in completeVisited:
continue
antibody, v = BFS(preGraph, postGraph, j, i)
completeVisited.extend(v)
if antibody == 1:
flag = True
break
else:
flag = False
if flag:
print("YES")
break
if not flag:
print("NO")
completeVisited : Repeating BFS (BFS search region is same with previous BFS) is interrupted
For “YES”, there should be at least one case of (antibody == 1)