์ด์ฝ”ํ…Œ Chapter 5 DFS/BFS (4)

๐Ÿ“Œ DFS/BFS ๊ฐœ๋… ๋ฐ ๊ธฐ์ดˆ ์˜ˆ์ œ

์ด์ฝ”ํ…Œ Chapter 5 DFS/BFS (1)
์ด์ฝ”ํ…Œ Chapter 5 DFS/BFS (2)
์ด์ฝ”ํ…Œ Chapter 5 DFS/BFS (3)

์‹ค์ „ ๋ฌธ์ œ 1: ์Œ๋ฃŒ์ˆ˜ ์–ผ๋ ค ๋จน๊ธฐ

Testcase 1

4 5
00110
00011
11111
00000
# 3

Testcase 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111
# 8

Solution

  • input๊ฐ’ ์‚ฌ์ด์— ๋„์–ด์“ฐ๊ธฐ๊ฐ€ ์—†๋‹ค๋Š” ์ ์„ ์ฃผ์˜ํ•˜์ž.
    ์Šต๊ด€์ ์œผ๋กœ input().split() ์“ฐ์ง€ ๋ง๊ณ  ๋ฌธ์ œ ์ž…๋ ฅ๊ฐ’ ํ™•์ธํ•ด์•ผ๊ฒ ๋‹ค.
  • DFS = ์žฌ๊ท€๋กœ ๊ตฌํ˜„!
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

def dfs(x, y):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x, y + 1)
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y - 1)
        return True
    return False

answer = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            answer += 1
print(answer)

์‹ค์ „ ๋ฌธ์ œ 2: ๋ฏธ๋กœ ํƒˆ์ถœ

Testcase

5 6
101010
111111
000001
111111
111111

Solution

  • ๊ตฌํ˜„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ƒํ•˜์ขŒ์šฐ ๋ฌธ์ œ๋ž‘ ์•ฝ๊ฐ„ ๋น„์Šทํ•˜๋‹ค.
  • BFS = deque ์ด์šฉ! (์‚ฌ์‹ค ๊ธฐ๋ณธ ๋ฆฌ์ŠคํŠธ๋กœ๋„ ํ’€ ์ˆ˜ ์žˆ๋Š”๋ฐ, ๊ต์žฌ์—์„œ deque์„ ๊ถŒ์žฅํ•˜๋‹ˆ ๋‹ค์Œ์—๋Š” deque์„ ์ด์šฉํ•ด๋ณด๋„๋ก ํ•˜์ž)
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):
    queue = [(x, y)]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dx[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            elif graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((x, y))
    return graph[n - 1][m - 1]

print(bfs(0, 0))

Feedback

  • ์•„์ง ์‹ค๋ ฅ์ด ๋ถ€์กฑํ•ด์„œ ๊ทธ๋Ÿฐ์ง€ ์˜ค๋ž˜ ๊ณ ๋ฏผํ•ด๋„ ๊ตฌํ˜„์ด๋‚˜ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์•„๋‹Œ ๊ฒฝ์šฐ ํ’€์ด๊ฐ€ ์ž˜ ๋– ์˜ค๋ฅด์ง€ ์•Š๋Š”๋‹ค.
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์œ ํ˜•๋ณ„๋กœ ํ’€๊ธฐ ์ „์—๋Š” ์–ด๋–ป๊ฒŒ๋“  ๊ทธ๋ƒฅ ํ’€์—ˆ๋˜ ๊ฒƒ ๊ฐ™์€๋ฐ, DFS๋กœ ํ’€์–ด์•ผ ๋ผ! DP๋กœ ํ’€์–ด์•ผ ๋ผ!๋ผ๋Š” ์ƒ๊ฐ์ด ์žˆ์œผ๋‹ˆ ๋” ๋ชป ํ‘ธ๋Š” ๊ฒƒ ๊ฐ™๊ธฐ๋„โ€ฆ
  • PART 02๊นŒ์ง€๋Š” ์œ ํ˜•์„ ์ตํžŒ๋‹ค๋Š” ๋Š๋‚Œ์œผ๋กœ ๊ณต๋ถ€ํ•˜๊ณ , PART 03๋ถ€ํ„ฐ๋Š” ๊ณ ๋ฏผํ•˜๋Š” ์‹œ๊ฐ„์„ ๋Š˜๋ ค๋ณด์ž

Source