[구름톤 챌린지] 4주차_ 19~ 20일차 학습

Day19 대체 경로 - 구름LEVEL (goorm.io)

내 풀이 과정

남은 2일치의 문제는 급한 일이 있어 24시간 이내에 해결해내지 못했다.

도시의 경로를 모두 구해 출력할 필요 없이 간단하게 출력해 낼 수 있다.

 

from collections import deque

def bfs(start, off):
	if start == off:
		return -1
	
	visited = [0] * (N + 1)
	q = deque([start])
	visited[start] = 1
	step = 1
	
	while q:
		step += 1
		for _ in range(len(q)):
			now = q.popleft()

			for to in graph[now]:
				if visited[to] or to == off:
					continue
					
				if to == E:
					return step
				
				visited[to] = 1
				q.append(to)
	
	return -1
	
N, M, S, E = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
	u, v = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)

for i in range(1, N + 1):
	print(bfs(S, i))

정해 코드

동일한 방식으로 해결했다 기존에 작성한 코드와 비교하며 수정하던 중 이전 코드를 지워버렸다ㅠㅠ 정해코드와 풀이 코드가 동일하다 

from collections import deque

def bfs(start, off):
	if start == off:
		return -1
	
	visited = [0] * (N + 1)
	q = deque([start])
	visited[start] = 1
	step = 1
	
	while q:
		step += 1
		for _ in range(len(q)):
			now = q.popleft()

			for to in graph[now]:
				if visited[to] or to == off:
					continue
					
				if to == E:
					return step
				
				visited[to] = 1
				q.append(to)
	
	return -1
	
N, M, S, E = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
	u, v = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)

for i in range(1, N + 1):
	print(bfs(S, i))

Day 연결 요소 제거하기 - 구름LEVEL (goorm.io)

내 풀이 과정

오늘문제는 참 쉬운문제인데 오류를 해결하지 못한채로 24시간이 지나버렸다.

기존에 이미 해결한 바와 같은 유형의 문제로 보여 응용하는 방식으로 해결했다. 

대신 동일 연결요소를 set()으로 저장하여 연결요소의 크기를 판단하는 방법을 택했다.

 

--마지막 2일차의 내 풀이코드가 컨테이너에서 사라지는 불상사가 발생하였다.

def f(i, j, c):
	arr[i][j] = c
	stack = [(i, j)]
	visited = set()
	
	while stack:
		y, x = stack.pop()
		
		if (y, x) in visited:
			continue
		
		visited.add((y, x))
		
		for k in range(4):
			ny, nx = y + dy[k], x + dx[k]
			
			if ny in (-1, N) or nx in (-1, N) or arr[ny][nx] != arr[y][x]:
				continue
			
			stack.append((ny, nx))
	
	if len(visited) >= K:
		for y, x in visited:
			arr[y][x] = "."

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

N, K, Q = map(int, input().split())
arr = [list(input()) for _ in range(N)]

for _ in range(Q):
	i, j, c = input().split()
	f(int(i) - 1, int(j) - 1, c)

for i in arr:
	print(''.join(i))

 

정해 코드

해설에서 설명하는 방식과 동일하게 풀어내었다.

 

def f(i, j, c):
	arr[i][j] = c
	stack = [(i, j)]
	visited = set()
	
	while stack:
		y, x = stack.pop()
		
		if (y, x) in visited:
			continue
		
		visited.add((y, x))
		
		for k in range(4):
			ny, nx = y + dy[k], x + dx[k]
			
			if ny in (-1, N) or nx in (-1, N) or arr[ny][nx] != arr[y][x]:
				continue
			
			stack.append((ny, nx))
	
	if len(visited) >= K:
		for y, x in visited:
			arr[y][x] = "."

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

N, K, Q = map(int, input().split())
arr = [list(input()) for _ in range(N)]

for _ in range(Q):
	i, j, c = input().split()
	f(int(i) - 1, int(j) - 1, c)

for i in arr:
	print(''.join(i))