음료수 얼려 먹기
NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4x5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.
내 답안
from collections import deque
n, m = map(int, input().split())
arr = []
for _ in range(n):
arr.append(list(map(int, input())))
count = 0
def bfs(arr, i, j):
global count
queue = deque([(i, j)])
while queue:
vi, vj = queue.popleft()
if vi >= n or vj >= m:
continue
if arr[vi][vj] == 0:
queue.append((vi+1, vj))
queue.append((vi, vj+1))
arr[vi][vj] = 1
else:
continue
count += 1
for i in range(n):
for j in range(m):
if arr[i][j] == 1:
continue
else:
bfs(arr, i, j)
print(count)
범위로 넓혀가면서 1이 나오면 멈춰야 한다고 판단하여 BFS라 생각했다.
큐를 사용하여 0인 칸을 찾은 뒤 해당 좌표를 큐에 넣는다.
큐에 있는 좌표를 하나씩 pop하여 해당 좌표를 기준으로 아래, 오른쪽 좌표를 큐에 추가하고 해당 좌표는 방문했으니 1로 변경한다.
좌표가 1인 경우 다음 큐에 있는 좌표로 넘어간다.
그렇게 큐에 있는 모든 좌표를 돌고 큐가 비어지면 하나의 아이스크림 개수인 count를 +1 한다.
두 번째 테스트 케이스에서 10이 나온다...ㅜ
답안 예시
책에서는 DFS로 풀이했다.
찾아보니 BFS로도 가능하다고 한다.
우선, DFS
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
def dfs(x, y):
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
if graph[x][y] == 0:
graph[x][y] = 1
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True
return False
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
result += 1
print(result)
- 특정한 지점의 주변 상, 하 , 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이몀ㄴ서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
- 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.
BFS의 풀이는 다음 게시글을 참고하였다.
미로 탈출
동빈이는 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는(1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
답안 예시
BFS 풀이
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
#현재 위치에서 네 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
#범위를 벗어난 경우 무시
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
#1이 아닌 0인 경우 무시
if graph[nx][ny] == 0:
continue
#1이라면 지나온 곳에 거리를 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph[n-1][m-1]
print(bfs(0, 0))
답안을 보니 이해가 되는 군...
내 답안은 없다.. 엄청 헤매서 제대로 결과가 나오지 않는다.. (물론 지금까지 내 답안들도 크게 다르지 않음...)
내가 접근했던 방법
처음에 상하좌우로 움직일 수 있어야 함
상하좌우의 좌표값을 append하고, 좌표의 값이 0이면 갈 수 없으니 append 하지 않음
지나온 곳을 0으로 변경하고 count +1을 함
범위 내에서만 이동할 수 있어야 함
문제: count로 체크를 하니 1이여서 방문했지만 막혀있던 칸도 개수를 셈
그래서 방향을 하, 우만 먼저 우선순위를 두고 그 다음 상, 좌도 갈 수 있도록 할지 고민함
큐에는 좌표값이 1인 좌표만 append하도록 수정, popletf() 좌표값이 append 되지 않으면 count -1
그러나 생각만큼 구현이 쉽지 않음
하면서 이게 맞는지 자꾸 의문이 들고 계속 막히는 기분이 들었다..
하나의 조건을 만족하면 또 다른 조건이 생겨나는 ....
count 사용&왔던 경로를 0으로 변경하는 것이 아니라 지나온 경로에 거리를 기록해야했다..
처음 BFS와 DFS 문제를 풀어봤던 만큼 계속해서 다른 문제들도 풀어가며 연습을 해야겠다!!
<출처>
이것이 취업을 위한 코딩테스트다 with 파이썬
'Coding > 이코테' 카테고리의 다른 글
[이코테]정렬 문제 풀이(성적이 낮은 순서로 학생 출력하기, 두 배열의 원소 교체) (0) | 2023.07.06 |
---|---|
[이코테]정렬 코드 정리 (0) | 2023.06.28 |
[이코테]DFS&BFS (0) | 2023.04.07 |
[이코테]구현 문제 풀이(시각, 왕실의 나이트, 게임 개발, 문자열 재정렬) (0) | 2023.04.07 |
[이코테]그리디 문제 풀이(큰 수의 법칙, 숫자 카드 게임) (0) | 2023.04.05 |