[leet130] DFS를 시작할 지점을 줄여보자

leetcode 130. Surrounded Regions
list를 set으로 바꿔 in function의 시간 단축

Question

모든 면이 X로 둘러싸인 O 지역은 X로 바꿔준다.
다만, 보더라인에 걸린 O 지역들(4면이 X가 아니라 3면 또는 2면만 X이기 때문에)은 그대로 남겨둔다.

Solution

DFS로 접근하면 편한 문제이지만, DFS의 시작점을 줄여서 소요 시간을 줄일 수 있다.

Solution 1

DFS를 도는 동안 보더라인을 통과하게 되면 check=True로 바꿔준다. 그리고 한번 DFS를 마쳤을 때 check가 False라면 O를 X로 바꿔줘야할 지점들이기 때문에 change list에 index를 추가해준다. dfs_helper를 포함한 풀 코드는 아래 깃허브 링크에서 확인 가능하다.

change = list()
for i in range(m):
	for j in range(n):
            if board[i][j] == 'O' and not visited_map[i][j]:
                dfs_helper(i,j)
                if not check: change += path
                path = list()
                check = False

for loc in change:
	board[loc[0]][loc[1]] = 'X'

Solution 2

애초에 DFS를 보더라인의 지점들에서만 시작한다. 그렇다면 모든 보더라인을 포함한 O를 들를 수 있었을 것이다. 마지막에 들렀던 지점들을 제외한 모든 지점을 X로 만들어준다. 이렇게 되면 보더라인을 포함하지 않는 O 지역들은 DFS를 아예 돌지 않기 때문에 시간을 단축할 수 있게 된다.

마찬가지로 full code는 아래 깃허브 solve2에서 확인할 수 있다. 또한 지나갔던 path에 in function을 적용해야 하기 때문에 set으로 type을 바꿔주어 시간을 단축한다.

for i in range(m):
        for j in range(n):
            if board[i][j] == 'O' and not visited_map[i][j] and (i==0 or j==0 or i==m-1 or j==n-1):
                dfs_helper(i,j)

path = set(path)            
for i in range(m):
	for j in range(n):
            if (i,j) not in path:
                board[i][j] = 'X'

모든 코드는 -> github

그 결과 시간이 꽤 단축되었다. visited_map을 다른 방식으로 만들어줬다면 시간을 좀 더 단축할 수 있었을 것이다.