'나'부터 깊이 우선 탐색을 실시한다. 탐색을 하면서 '나'가 아니고 방문하지 않았을 경우, 촌수를 더해준다. visited라는 리스트를 만들어서 인덱스 값에 촌수를 저장하도록 하였다.
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n = int(input())
a,b = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
for i in range(m):
x,y = map(int, input().split())
graph[x].append(y)
graph[y].append(x)
visited = [0] * (n+1)
def dfs(started):
for i in graph[started]:
if i != a and not visited[i] :
visited[i] = visited[started] + 1
dfs(i)
dfs(a)
if visited[b] == 0:
print(-1)
else:
print(visited[b])
대각선을 제외한 상하좌우의 이동경로를 설정한다. count라는 변수를 지정해 깊이 우선 탐색시 단지내 아파트에 방문할 때마다 1씩 증가시켜주면서 단지 탐색이 끝날 시 리스트에 넣어준다. 이때 단지를 탐색할 시에는 방문한 아파트는 0으로 지정하여 중복으로 세는 것을 방지한다. 리스트에 넣어준 후, count를 초기화시켜주면서 다음 단지로 이동한다.
n = int(input())
graph = []
num = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def dfs(x, y):
if x < 0 or x >= n or y < 0 or y >= n:
return False
if graph[x][y] == 1:
global count
count += 1
graph[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
dfs(nx, ny)
return True
count = 0
for i in range(n):
for j in range(n):
if dfs(i, j) == True:
num.append(count)
count = 0
num.sort()
print(len(num))
for i in range(len(num)):
print(num[i])
다른 문제들처럼 지도나 종이 밖으로 나가지 않도록 하는 조건을 걸어주는 것이 아닌 모눈종이 안에서 방문하지 않은 부분이 있으면 개수를 세어야 한다. 직사각형은 1을 부여하여 영역을 구분하도록 하였다. 타인의 코드를 참고하였다.
import sys
sys.setrecursionlimit(10000)
def dfs(y, x, cnt):
graph[y][x] = 1
for dy, dx in d:
Y, X = y+dy, x+dx
if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
cnt = dfs(Y, X, cnt+1)
return cnt
M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
for _ in range(K):
x1, y1, x2, y2 = map(int, input().split())
for i in range(y1, y2):
for j in range(x1, x2):
graph[i][j] = 1
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = []
for i in range(M):
for j in range(N):
if graph[i][j] == 0:
res.append(dfs(i, j, 1))
print(len(res))
print(*sorted(res))
2583번과 유사한 문제였다. dfs로 문제를 해결했으나, 메모리 초과를 만나게 되었다. 구글링을 통해서 메모리 초과일 경우, bfs로 해결을 한다고 한다. bfs는 학습하기는 했지만, 겉핥기 식으로 한 것 같아서 조금 더 학습해본 후, 문제를 다시 풀어보어야겠다.
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
drawing_paper = [list(map(int, input().split())) for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
count = 0
pic= []
def dfs(x,y):
if x < 0 or x >= n or y < 0 or y >= m:
return False
if drawing_paper[x][y] == 1:
global count
count += 1
drawing_paper[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
dfs(nx, ny)
return True
for i in range(n):
for j in range(m):
if drawing_paper[i][j] == 1:
dfs(i,j)
pic.append(count)
count = 0
print(len(pic))
if len(pic) == 0:
print(0)
else:
print(max(pic))
물통에서 물을 옮기는 과정은 a -> b, a -> c, b -> a, b -> c, c -> a, c -> b 총 6가지이다. 경우의 수를 고려하여 각 과정에서의 조건을 판단하여 구현한다. a -> b로 물을 옮기는 경우를 예를 들어보자.
A물통과 B물통에 들어 있는 물이 B물통의 용량보다 크다면, B물통에는 용량만큼 물이 들어가게 되고, A물통에는 A물통과 B물통에 들어 있는 물에서 B물통의 용량만큼 빼준 물의 양이 담기게 된다.
반대로 A물통과 B물통에 들어 있는 물이 B물통의 용량보다 작다면, 모든 물이 B물통에 담기게 된다. dfs를 반복하면서 A물통이 0이 되면, True
를 찍어준다.
def dfs(ca, cb, cc):
if visited[ca][cb] == True:
return;
if ca == 0:
ans[cc] = True
visited[ca][cb] = True
# a -> b
if ca + cb > b:
dfs((ca + cb) - b, b, cc)
else:
dfs(0, ca + cb, cc)
# b -> a
if cb + ca > a:
dfs(a, (cb + ca) - a, cc);
else:
dfs(cb + ca, 0, cc)
# c -> a
if cc + ca > a:
dfs(a, cb, (cc + ca) - a)
else:
dfs(cc + ca, cb, 0)
# c -> b
if cc + cb > b:
dfs(ca, b, (cc + cb) - b)
else:
dfs(ca, cc + cb, 0)
# b -> c, a -> c
# a + b = c
dfs(ca, 0, cb + cc)
dfs(0, cb, ca + cc)
ans = [False] *201
visited = [[False for _ in range(201)]for _ in range(201)]
a,b,c = map(int, input().split())
dfs(0,0,c)
for i in range(len(ans)):
if ans[i] == True:
print(i, end=" ")