Algorithm Problem/Python

[python] SWEA - 1226. [S/W ๋ฌธ์ œํ•ด๊ฒฐ ๊ธฐ๋ณธ] 7์ผ์ฐจ - ๋ฏธ๋กœ1

deo2kim 2020. 8. 10. 08:03
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

1. D4 | DFS

2. ์‹œ์ž‘์ ์„ ์ฐพ๋Š”๋‹ค.

3. ์Šคํƒ์„ ํ™œ์šฉํ•˜๊ณ  ์ƒํ•˜์ขŒ์šฐ 4๋ฐฉํ–ฅ ํƒ์ƒ‰(์ธ๋ฑ์Šค ๋ฒ”์œ„ ์ด๋‚ด)์„ ํ•œ๋‹ค.

 (1) ๊ธธ('0')์„ ๋งŒ๋‚  ๊ฒฝ์šฐ ์Šคํƒ์— ์ถ”๊ฐ€ํ•˜๊ณ , ๋‚˜์ค‘์— ๋‹ค์‹œ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์„ ๋ฐฉ์ง€ํ•˜๊ธฐ ์œ„ํ•ด ๊ทธ ์ง€์ ์˜ ๊ฐ’์„ ๋ฐ”๊ฟ”์ค€๋‹ค.

 (2) ๋('3')์„ ๋งŒ๋‚  ๊ฒฝ์šฐ ๋ฏธ๋กœ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ์˜๋ฏธ ์ด๋ฏ€๋กœ ๋‹ต์„ 1๋กœ ํ•˜๊ณ  ํƒ์ƒ‰์„ ์ข…๋ฃŒํ•œ๋‹ค.

 

๐Ÿ’จ DFS ๊ธฐ๋ณธ๋ฌธ์ œ์ด๋‹ค.

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for _ in range(10):
    answer = 0
    n = int(input())
    maps = [list(input()) for _ in range(16)]

    # ์ถœ๋ฐœ์  ์ฐพ๊ธฐ
    x, y = 0, 0
    for i in range(16):
        for j in range(16):
            if maps[i][j] == '2':
                x, y = i, j

    # ๋ฏธ๋กœํƒ์ƒ‰ DFS
    stack = [(x, y)]
    while stack:
        cx, cy = stack.pop()
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0 <= nx < 16 and 0 <= ny < 16:
                # ๊ธธ์„ ๋งŒ๋‚  ๊ฒฝ์šฐ
                if maps[nx][ny] == '0':
                    stack.append((nx, ny))
                    maps[nx][ny] = '9'
                # ๋์ ์„ ๋งŒ๋‚  ๊ฒฝ์šฐ 
                elif maps[nx][ny] == '3':
                    answer = 1
                    stack.clear()
                    break

    print('#{} {}'.format(n, answer))

 

์ถœ์ฒ˜: SW Expert Academy

๋ฌธ์ œ: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE

 

SW Expert Academy

SW ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์—ญ๋Ÿ‰ ๊ฐ•ํ™”์— ๋„์›€์ด ๋˜๋Š” ๋‹ค์–‘ํ•œ ํ•™์Šต ์ปจํ…์ธ ๋ฅผ ํ™•์ธํ•˜์„ธ์š”!

swexpertacademy.com

๐Ÿ“•๋ฌธ์ œ ํ™•์ธํ•˜๊ธฐ๐Ÿ”ป๐Ÿ”ป

๋”๋ณด๊ธฐ

์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์€ ๋ฏธ๋กœ๊ฐ€ ์žˆ๋‹ค. 16*16 ํ–‰๋ ฌ์˜ ํ˜•ํƒœ๋กœ ๋งŒ๋“ค์–ด์ง„ ๋ฏธ๋กœ์—์„œ ํฐ์ƒ‰ ๋ฐ”ํƒ•์€ ๊ธธ, ๋…ธ๋ž€์ƒ‰ ๋ฐ”ํƒ•์€ ๋ฒฝ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.

๊ฐ€์žฅ ์ขŒ์ƒ๋‹จ์— ์žˆ๋Š” ์นธ์„ (0, 0)์˜ ๊ธฐ์ค€์œผ๋กœ ํ•˜์—ฌ, ๊ฐ€๋กœ๋ฐฉํ–ฅ์„ x ๋ฐฉํ–ฅ, ์„ธ๋กœ๋ฐฉํ–ฅ์„ y ๋ฐฉํ–ฅ์ด๋ผ๊ณ  ํ•  ๋•Œ, ๋ฏธ๋กœ์˜ ์‹œ์ž‘์ ์€ (1, 1)์ด๊ณ  ๋„์ฐฉ์ ์€ (13, 13)์ด๋‹ค.

์ฃผ์–ด์ง„ ๋ฏธ๋กœ์˜ ์ถœ๋ฐœ์ ์œผ๋กœ๋ถ€ํ„ฐ ๋„์ฐฉ์ง€์ ๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด ์žˆ๋Š”์ง€ ํŒ๋‹จํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜๋ผ.

์•„๋ž˜์˜ ์˜ˆ์‹œ์—์„œ๋Š” ๋„๋‹ฌ ๊ฐ€๋Šฅํ•˜๋‹ค.


 

 

 


์•„๋ž˜์˜ ์˜ˆ์‹œ์—์„œ๋Š” ์ถœ๋ฐœ์ ์ด (1, 1)์ด๊ณ , ๋„์ฐฉ์ ์ด (11, 11)์ด๋ฉฐ ๋„๋‹ฌ์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค.


[์ž…๋ ฅ]

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ๋ฐ”๋กœ ๋‹ค์Œ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

์ด 10๊ฐœ์˜ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์—์„œ 1์€ ๋ฒฝ์„ ๋‚˜ํƒ€๋‚ด๋ฉฐ 0์€ ๊ธธ, 2๋Š” ์ถœ๋ฐœ์ , 3์€ ๋„์ฐฉ์ ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.

[์ถœ๋ ฅ]

#๋ถ€ํ˜ธ์™€ ํ•จ๊ป˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๋ฒˆํ˜ธ๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๊ณต๋ฐฑ ๋ฌธ์ž ํ›„ ๋„๋‹ฌ ๊ฐ€๋Šฅ ์—ฌ๋ถ€๋ฅผ 1 ๋˜๋Š” 0์œผ๋กœ ํ‘œ์‹œํ•œ๋‹ค (1 - ๊ฐ€๋Šฅํ•จ, 0 - ๊ฐ€๋Šฅํ•˜์ง€ ์•Š์Œ).

๋ฐ˜์‘ํ˜•