백준 4963. 섬의 개수 (파이썬- DFS, BFS)

문제를 요약하면..

흔한 DFS, BFS의 문제인 연결요소 개수를 구하는 것이다.

단, 상하좌우 뿐만 아니라 대각선 경우도 연결되어있다!

시도 1. DFS 이용 (정답)

무한 재귀호출 방지를 위해 sys.setrecursionlimit(10000)을 꼭 써줘야 한다.

코드가 맞더라도 이것 때문에 런타임에러 걸린다..

백준 문제를 풀 때, 재귀호출이 발생할 경우 이 코드는 꼭 넣어야 런타임 에러가 안걸리는 것 같다.

시도 2. BFS 이용 (정답)

※은근히 헷갈리는 것※

queue = deque([(x,y)])

반드시 리스트 안 tuple () 처리해서 추가해준다.

이 후 queue.append() 할 때는 (x,y)로 묶어서 추가해줘야 한다.

queue.append(x,y) X

queue.append([x,y]) X

queue.apppend((x,y)) X

시도 3. BFS ( 정답)

BFS를 이용하며, visited 리스트 사용 안하기

문제를 풀다보면 visited 리스트가 꼭 없어도 될 때가 있다.

그냥 graph내에서 해결하고 싶은데 방문한 흔적은 남겨야 하고..

그럴 땐, graph에서 1인 것만 탐색해야 하니까

1인 위치를 방문했으면 0으로 바꿔주거나 2 값으로 바꿔주면 된다. 즉, 1 외 내가 설정하고 싶은 값으로 바꿔주면 된다!

생각보다 간단하며 코드도 보면 뭔가 간단해진 느낌이다.