๐Ÿ”จ ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ

๋ฐฑ์ค€ Class4 Gold4

solved_ac[Class4] ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ

๋ฌธ์ œ


Nร—M์˜ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„๋˜๋Š” ๋งต์ด ์žˆ๋‹ค. ๋งต์—์„œ 0์€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ด๊ณ , 1์€ ์ด๋™ํ•  ์ˆ˜ ์—†๋Š” ๋ฒฝ์ด ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹น์‹ ์€ (1, 1)์—์„œ (N, M)์˜ ์œ„์น˜๊นŒ์ง€ ์ด๋™ํ•˜๋ ค ํ•˜๋Š”๋ฐ, ์ด๋•Œ ์ตœ๋‹จ ๊ฒฝ๋กœ๋กœ ์ด๋™ํ•˜๋ ค ํ•œ๋‹ค. ์ตœ๋‹จ๊ฒฝ๋กœ๋Š” ๋งต์—์„œ ๊ฐ€์žฅ ์ ์€ ๊ฐœ์ˆ˜์˜ ์นธ์„ ์ง€๋‚˜๋Š” ๊ฒฝ๋กœ๋ฅผ ๋งํ•˜๋Š”๋ฐ, ์ด๋•Œ ์‹œ์ž‘ํ•˜๋Š” ์นธ๊ณผ ๋๋‚˜๋Š” ์นธ๋„ ํฌํ•จํ•ด์„œ ์„ผ๋‹ค.

๋งŒ์•ฝ์— ์ด๋™ํ•˜๋Š” ๋„์ค‘์— ํ•œ ๊ฐœ์˜ ๋ฒฝ์„ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๋Š” ๊ฒƒ์ด ์ข€ ๋” ๊ฒฝ๋กœ๊ฐ€ ์งง์•„์ง„๋‹ค๋ฉด, ๋ฒฝ์„ ํ•œ ๊ฐœ ๊นŒ์ง€ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜์—ฌ๋„ ๋œ๋‹ค.

ํ•œ ์นธ์—์„œ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์€ ์ƒํ•˜์ขŒ์šฐ๋กœ ์ธ์ ‘ํ•œ ์นธ์ด๋‹ค.

๋งต์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•ด ๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ


์ฒซ์งธ ์ค„์— N(1 โ‰ค N โ‰ค 1,000), M(1 โ‰ค M โ‰ค 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์— M๊ฐœ์˜ ์ˆซ์ž๋กœ ๋งต์ด ์ฃผ์–ด์ง„๋‹ค. (1, 1)๊ณผ (N, M)์€ ํ•ญ์ƒ 0์ด๋ผ๊ณ  ๊ฐ€์ •ํ•˜์ž.

์ถœ๋ ฅ


์ฒซ์งธ ์ค„์— ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋ถˆ๊ฐ€๋Šฅํ•  ๋•Œ๋Š” -1์„ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

6 4
0100
1110
1000
0000
0111
0000

์˜ˆ์ œ ์ถœ๋ ฅ 1

15

์˜ˆ์ œ ์ž…๋ ฅ 2

4 4
0111
1111
1111
1110

์˜ˆ์ œ ์ถœ๋ ฅ 2

-1

๐Ÿ“– ์ž๋ฃŒ๊ตฌ์กฐ

[BFS + ๊ตฌํ˜„]์ด์—ˆ๋‹ค. ๋‹ค๋งŒ ๊ทธ ๊ตฌํ˜„ ๋ถ€๋ถ„์ด ๋ฌด์ฒ™ ์–ด๋ ค์› ๋‹ค.

TRY 1

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2022-07-11 แ„‹แ…ฉแ„’แ…ฎ 7 05 57

์ฒ˜์Œ์—๋Š” Brute Force๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค. ๋ชจ๋“  ๋ฒฝ์— ๋Œ€ํ•˜์—ฌ ํ•œ ๋ฒˆ์”ฉ ์ œ๊ฑฐํ•ด๋ณด๋ฉฐ ์ œ์ผ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

๐Ÿ‘‰๐Ÿป ์‹œ๊ฐ„ ์ดˆ๊ณผ

TRY 2

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-14

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-15

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-16

โ€œTRY 1โ€์—์„œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜๋Š” ์ด์œ ๋Š” ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(N^2)์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์ด๋ฅผ ์ค„์—ฌ์•ผ ํ•˜๋Š”๋ฐ ๋„์ €ํžˆ ์ƒ๊ฐ์ด ์•ˆ ๋‚ฌ๋‹ค.

๋™ํ˜์ด๊ฐ€ <3์ฐจ์›>์ด๋ผ๋Š” ํžŒํŠธ๋ฅผ ์ค˜์„œ ์ด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๋‹ค์‹œ ์ƒ๊ฐ์„ ํ•ด ๋ณด์•˜๋‹ค.

  • ๋ฒฝ์„ ์•ˆ ๋ถ€์ˆ˜๋Š” ๊ฒฝ์šฐ์˜ ๋งต
  • ๋ฒฝ์„ ๋ถ€์ˆ˜๋Š” ๊ฒฝ์šฐ์˜ ๋งต

์ด๋ ‡๊ฒŒ ๋‘ ๊ฐ€์ง€๋กœ ๋‚˜๋ˆ„์–ด์„œ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•˜๋ฉด ๋˜์ง€ ์•Š์„๊นŒ ํ•˜๊ณ  ์ง„ํ–‰ ๊ณผ์ •์„ ๊ทธ๋ ค๋ณด์•˜๋‹ค.

๊ธธ ํ˜น์€ ๋ฒฝ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ๋ถ„ํ™์ƒ‰ ์ˆซ์ž๊ฐ€ ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋ฅผ ์˜๋ฏธํ•œ๋‹ค.

ํ•˜์ง€๋งŒ ์ด๋ ‡๊ฒŒ ํ–ˆ์„ ๊ฒฝ์šฐ ๋ฒฝ์„ 2๋ฒˆ ์ด์ƒ ๋ถ€์ˆ˜๊ฒŒ ๋˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋ฐœ์ƒํ•˜์—ฌ ์˜ค๋‹ต์ด๋‹ค.

๐Ÿ‘‰๐Ÿป ์˜ค๋‹ต

TRY 3

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-17

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-18

แ„‹แ…งแ†ซแ„‰แ…ณแ†ธแ„Œแ…กแ†ผ-19

์‹œ๊ฐ„ ๊ด€๊ณ„์ƒ ๊ฒฐ๊ตญ ์†”๋ฃจ์…˜์„ ์ฐธ๊ณ ํ•˜์˜€๋‹ค. https://hongcoding.tistory.com/18

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป CODE

TRY 1

import sys
from collections import deque
import copy
input = sys.stdin.readline
N,M = map(int,input().split())


graph = [[0]*M for _ in range(N)]

# ๋งต ์ƒ์„ฑ
for i in range(N):
    line = input()
    for j in range(M):
        graph[i][j] = int(line[j])

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

# BFS๋กœ ์ตœ๋‹จ๊ฑฐ๋ฆฌ ํƒ์ƒ‰
def bfs(a,b,graph):
    q = deque([(a,b)])

    while q:
        x,y = q.popleft()

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if 0<=nx<N and 0<=ny<M and graph[nx][ny] == 0:
                q.append((nx,ny))
                graph[nx][ny] = graph[x][y] + 1

lst_answer = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            temp = copy.deepcopy(graph)
            temp[i][j] = 0
            bfs(0,0,temp)
            
            if temp[N-1][M-1] == 0:
                continue
            
            lst_answer.append(temp[N-1][M-1]+1)

if not lst_answer:
    print(-1)
else:
    print(min(lst_answer))

TRY 3

import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())

graph = [[0]*M for _ in range(N)]
# visited[x][y][0] --> ๋ฒฝ ํŒŒ๊ดด ๊ธฐํšŒ O
# visited[x][y][1] --> ๋ฒฝ ํŒŒ๊ดด ๊ธฐํšŒ X
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]

# ๋งต ์ƒ์„ฑ
for i in range(N):
    line = input()
    for j in range(M):
        graph[i][j] = int(line[j])


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

# BFS๋กœ ์ตœ๋‹จ๊ฑฐ๋ฆฌ ํƒ์ƒ‰
def bfs(a,b,c):
    visited[a][b][c] = 1
    q = deque([(a,b,c)])

    while q:
        x,y,z = q.popleft()

        # ๋ ์ง€์  ๋„๋‹ฌ
        if x == N-1 and y == M-1:
            return visited[x][y][z]

        # ์ƒํ•˜์ขŒ์šฐ ํƒ์ƒ‰ ํ•ด๋ด„
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if 0<=nx<N and 0<=ny<M and visited[nx][ny][z] == 0:
                # Case1. ๋ฒฝ & ๋ฒฝ ํŒŒ๊ดด ๊ธฐํšŒ O
                # --> (nx,ny) ๋ฒฝ ํŒŒ๊ดด ๊ธฐํšŒ ์‚ญ์ œ & ํ์— ์ถ”๊ฐ€(์ด๋™)
                if graph[nx][ny] == 1 and z == 0:
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    q.append((nx,ny,1))

                # Case2. ๋ฒฝ & ๋ฒฝ ํŒŒ๊ดด ๊ธฐํšŒ X
                # --> ์ด๋™ ๋ถˆ๊ฐ€

                # Case3. ๊ธธ
                # --> ์ด๋™
                if graph[nx][ny] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    q.append((nx,ny,z))
    
    return -1

print(bfs(0,0,0))

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6