[코테 적용] [1번 문제] 완전 탐색

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

문제

(https://leetcode.com/problems/number-of-islands/)

접근방법

• 눈으로는 바로 알 수 있지만 컴퓨터한테 시켜야한다.
• 어떻게 내가 인식했지라고 생각
• 사고방식을 쪼개서 직관적으로 생각하는 방법을 연습
• 이런 문제는 bfs dfs 기본문제라 당연히 알고있어야한다.
• 암시적 그래프 표현
• 2차원 배열에 지도를 표현한다 -> 그래프를 표현할 수 있다.모든 곳을 탐방 -> bfs,dfs

코드 설계

코드 구현

• BFS - deque 템플릿
  

from collections import deque

def numIslands(grid):
    number_of_islands = 0
    row = len(grid)
    col = len(grid[0])
    visited = [
        [False] * col
        for _ in range(row)
    ]
    
    def bfs(x, y):
        # 3, 5 -> 2, 5 -> 4, 5 -> 3, 4 (상,하,좌,우)
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1 ,1]        
        visited[x][y] = True
        queue = deque()
        queue.append((x, y))
        
        while queue:
            cur_x, cur_y = queue.popleft()
            for i in range(4):
                next_x = cur_x + dx[i]
                next_y = cur_y + dy[i]
                if next_x >= 0 and next_x < row and next_y >= 0 and next_y < col: # 참조할 수 없는 영역일 때 방문 X, 
                    if grid[next_x][next_y] == "1" and not visited[next_x][next_y]: # visited X, 물 X
                        visited[next_x][next_y] = True
                        queue.append((next_x, next_y))
            
    for i in range(row):
        for j in range(col):
            if grid[i][j] == "1" and not visited[i][j]:
                bfs(i, j)
                number_of_islands += 1
                
    return number_of_islands


print(numIslands(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]))

• 동서남북 방문법 (상하좌우)
  

• 동서남북+대각선 방문법