728x90
반응형
※ 문제링크
해당 문제는 BFS를 사용해서 해결할 수 있는 문제였다. 문제에서 상,하,좌,우 뿐만아니라 대각선까지도 이동가능하다는 점만 신경써서 코드를 작성하면 비교적 간단하게 해결할 수 있어서 해당방식으로 코드를 작성하였다. 자세한 풀이방법과 코드는 아래와 같다.
1. 입력값을 바탕으로 2차원 배열로 지도형태를 구현한다.
2. 이어져 있는 섬들을 탐색할 수 있는 BFS함수를 작성한다.(방문한 섬의 경우 2로 변경하여 방문여부를 표기했다.)
3. 배열의 크기만큼 반복문으로 탐색을 하면서 방문하지 않은 섬이 나올 때마다 BFS함수를 실행하고 cnt에 +1을 해준다.
4. 지도의 모든 좌표를 탐색한 후 결과값을 출력한다.
+ 해당문제는 종료조건을 입력받기 전까지 계속 실행해야하는 것을 유의하여 코드를 짜야한다.
+ 입력값이 많아 sys함수로 입력값을 받았다. sys함수 사용시에는 개행문자에 유의하자
from collections import deque
import sys
while True:
# input = sys.stdin.readline
w, h = map(int, input().split()) # w: x좌표 / h: y좌표
if w == 0 and h == 0:
break
field = []
for _ in range(h):
field.append(list(map(int, input().split())))
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
def bfs(x, y):
queue = deque()
queue.append([x, y])
field[y][x] = 2
while queue:
x, y = queue.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == 1:
field[ny][nx] = 2
queue.append([nx, ny])
cnt = 0
for x in range(w):
for y in range(h):
if field[y][x] == 1:
bfs(x, y)
cnt += 1
print(cnt)
P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 10026번 적록색약 / 사용언어 : 파이썬(python) (0) | 2022.01.15 |
---|---|
[BOJ] 1753번 최단경로 / 사용언어 : 파이썬(python) (0) | 2022.01.15 |
[BOJ] 18352번 특정 거리의 도시 찾기 / 사용언어 : 파이썬(python) (0) | 2022.01.14 |
[BOJ] 14502번 연구소 / 사용언어 : 파이썬(python) (0) | 2022.01.14 |
[BOJ] 11724번 연결 요소의 개수 / 사용언어 : 파이썬(python) (0) | 2022.01.13 |
댓글