๐Ÿฆ  ๊ฑฐ๋ฆฌ๋‘๊ธฐ ํ™•์ธํ•˜๊ธฐ

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค Level2

[Level2] ๊ฑฐ๋ฆฌ๋‘๊ธฐ ํ™•์ธํ•˜๊ธฐ

๋ฌธ์ œ ์„ค๋ช…


๊ฐœ๋ฐœ์ž๋ฅผ ํฌ๋งํ•˜๋Š” ์ฃ ๋ฅด๋””๊ฐ€ ์นด์นด์˜ค์— ๋ฉด์ ‘์„ ๋ณด๋Ÿฌ ์™”์Šต๋‹ˆ๋‹ค.

์ฝ”๋กœ๋‚˜ ๋ฐ”์ด๋Ÿฌ์Šค ๊ฐ์—ผ ์˜ˆ๋ฐฉ์„ ์œ„ํ•ด ์‘์‹œ์ž๋“ค์€ ๊ฑฐ๋ฆฌ๋ฅผ ๋‘ฌ์„œ ๋Œ€๊ธฐ๋ฅผ ํ•ด์•ผํ•˜๋Š”๋ฐ ๊ฐœ๋ฐœ ์ง๊ตฐ ๋ฉด์ ‘์ธ ๋งŒํผ ์•„๋ž˜์™€ ๊ฐ™์€ ๊ทœ์น™์œผ๋กœ ๋Œ€๊ธฐ์‹ค์— ๊ฑฐ๋ฆฌ๋ฅผ ๋‘๊ณ  ์•‰๋„๋ก ์•ˆ๋‚ดํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. 1. ๋Œ€๊ธฐ์‹ค์€ 5๊ฐœ์ด๋ฉฐ, ๊ฐ ๋Œ€๊ธฐ์‹ค์€ 5x5 ํฌ๊ธฐ์ž…๋‹ˆ๋‹ค. 2. ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์œ„ํ•˜์—ฌ ์‘์‹œ์ž๋“ค ๋ผ๋ฆฌ๋Š” ๋งจํ•ดํŠผ ๊ฑฐ๋ฆฌ1๊ฐ€ 2 ์ดํ•˜๋กœ ์•‰์ง€ ๋ง์•„ ์ฃผ์„ธ์š”. 3. ๋‹จ ์‘์‹œ์ž๊ฐ€ ์•‰์•„์žˆ๋Š” ์ž๋ฆฌ ์‚ฌ์ด๊ฐ€ ํŒŒํ‹ฐ์…˜์œผ๋กœ ๋ง‰ํ˜€ ์žˆ์„ ๊ฒฝ์šฐ์—๋Š” ํ—ˆ์šฉํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด,

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2022-08-02 แ„‹แ…ฉแ„Œแ…ฅแ†ซ 3 41 23

5๊ฐœ์˜ ๋Œ€๊ธฐ์‹ค์„ ๋ณธ ์ฃ ๋ฅด๋””๋Š” ๊ฐ ๋Œ€๊ธฐ์‹ค์—์„œ ์‘์‹œ์ž๋“ค์ด ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ž˜ ๊ธฐํ‚ค๊ณ  ์žˆ๋Š”์ง€ ์•Œ๊ณ  ์‹ถ์–ด์กŒ์Šต๋‹ˆ๋‹ค. ์ž๋ฆฌ์— ์•‰์•„์žˆ๋Š” ์‘์‹œ์ž๋“ค์˜ ์ •๋ณด์™€ ๋Œ€๊ธฐ์‹ค ๊ตฌ์กฐ๋ฅผ ๋Œ€๊ธฐ์‹ค๋ณ„๋กœ ๋‹ด์€ 2์ฐจ์› ๋ฌธ์ž์—ด ๋ฐฐ์—ด places๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฐ ๋Œ€๊ธฐ์‹ค๋ณ„๋กœ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์œผ๋ฉด 1์„, ํ•œ ๋ช…์ด๋ผ๋„ ์ง€ํ‚ค์ง€ ์•Š๊ณ  ์žˆ์œผ๋ฉด 0์„ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด ์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ


  • places์˜ ํ–‰ ๊ธธ์ด(๋Œ€๊ธฐ์‹ค ๊ฐœ์ˆ˜) = 5
    • places์˜ ๊ฐ ํ–‰์€ ํ•˜๋‚˜์˜ ๋Œ€๊ธฐ์‹ค ๊ตฌ์กฐ๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
  • places์˜ ์—ด ๊ธธ์ด(๋Œ€๊ธฐ์‹ค ์„ธ๋กœ ๊ธธ์ด) = 5
  • places์˜ ์›์†Œ๋Š” P,O,X๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด์ž…๋‹ˆ๋‹ค.
    • places ์›์†Œ์˜ ๊ธธ์ด(๋Œ€๊ธฐ์‹ค ๊ฐ€๋กœ ๊ธธ์ด) = 5
    • P๋Š” ์‘์‹œ์ž๊ฐ€ ์•‰์•„์žˆ๋Š” ์ž๋ฆฌ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
    • O๋Š” ๋นˆ ํ…Œ์ด๋ธ”์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
    • X๋Š” ํŒŒํ‹ฐ์…˜์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
  • ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” 5๊ฐœ ๋Œ€๊ธฐ์‹ค์˜ ํฌ๊ธฐ๋Š” ๋ชจ๋‘ 5x5 ์ž…๋‹ˆ๋‹ค.
  • return ๊ฐ’ ํ˜•์‹
    • 1์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด์— 5๊ฐœ์˜ ์›์†Œ๋ฅผ ๋‹ด์•„์„œ return ํ•ฉ๋‹ˆ๋‹ค.
    • places์— ๋‹ด๊ฒจ ์žˆ๋Š” 5๊ฐœ ๋Œ€๊ธฐ์‹ค์˜ ์ˆœ์„œ๋Œ€๋กœ, ๊ฑฐ๋ฆฌ๋‘๊ธฐ ์ค€์ˆ˜ ์—ฌ๋ถ€๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ๋ฐฐ์—ด์— ๋‹ด์Šต๋‹ˆ๋‹ค.
    • ๊ฐ ๋Œ€๊ธฐ์‹ค ๋ณ„๋กœ ๋ชจ๋“  ์‘์‹œ์ž๊ฐ€ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์œผ๋ฉด 1์„, ํ•œ ๋ช…์ด๋ผ๋„ ์ง€ํ‚ค์ง€ ์•Š๊ณ  ์žˆ์œผ๋ฉด 0์„ ๋‹ด์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ


แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2022-08-02 แ„‹แ…ฉแ„Œแ…ฅแ†ซ 3 43 37

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

์ฒซ ๋ฒˆ์งธ ๋Œ€๊ธฐ์‹ค

.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P
  • ๋ชจ๋“  ์‘์‹œ์ž๊ฐ€ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ ๋Œ€๊ธฐ์‹ค

No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P
  • (0, 0) ์ž๋ฆฌ์˜ ์‘์‹œ์ž์™€ (2, 0) ์ž๋ฆฌ์˜ ์‘์‹œ์ž๊ฐ€ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • (1, 2) ์ž๋ฆฌ์˜ ์‘์‹œ์ž์™€ (0, 3) ์ž๋ฆฌ์˜ ์‘์‹œ์ž๊ฐ€ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • (4, 3) ์ž๋ฆฌ์˜ ์‘์‹œ์ž์™€ (4, 4) ์ž๋ฆฌ์˜ ์‘์‹œ์ž๊ฐ€ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

์„ธ ๋ฒˆ์งธ ๋Œ€๊ธฐ์‹ค

No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X
  • ๋ชจ๋“  ์‘์‹œ์ž๊ฐ€ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.

๋„ค ๋ฒˆ์งธ ๋Œ€๊ธฐ์‹ค

No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O
  • ๋Œ€๊ธฐ์‹ค์— ์‘์‹œ์ž๊ฐ€ ์—†์œผ๋ฏ€๋กœ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.

๋‹ค์„ฏ ๋ฒˆ์งธ ๋Œ€๊ธฐ์‹ค

No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P
  • ๋ชจ๋“  ์‘์‹œ์ž๊ฐ€ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๋ฅผ ์ง€ํ‚ค๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ ๋Œ€๊ธฐ์‹ค์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋Œ€๊ธฐ์‹ค์—์„œ ๊ฑฐ๋ฆฌ๋‘๊ธฐ๊ฐ€ ์ง€์ผœ์ง€๊ณ  ์žˆ์œผ๋ฏ€๋กœ, ๋ฐฐ์—ด [1, 0, 1, 1, 1]์„ return ํ•ฉ๋‹ˆ๋‹ค.

์ œํ•œ์‹œ๊ฐ„ ์•ˆ๋‚ด

  • ์ •ํ™•์„ฑ ํ…Œ์ŠคํŠธ : 10์ดˆ

โ€ป ๊ณต์ง€ - 2022๋…„ 4์›” 25์ผ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๊ฐ€ ์ถ”๊ฐ€๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

๋‘ ํ…Œ์ด๋ธ” T1, T2๊ฐ€ ํ–‰๋ ฌ (r1, c1), (r2, c2)์— ๊ฐ๊ฐ ์œ„์น˜ํ•˜๊ณ  ์žˆ๋‹ค๋ฉด, T1, T2 ์‚ฌ์ด์˜ ๋งจํ•ดํŠผ ๊ฑฐ๋ฆฌ๋Š” |r1 - r2| + |c1 - c2| ์ž…๋‹ˆ๋‹ค.

๐Ÿ“– ๊ฐ€์ ธ๋‹ค ์“ฐ๊ธฐ

์ฒ˜์Œ์—๋Š” BFS๋กœ ์ ‘๊ทผํ•˜์˜€๋‹ค.

แ„‚แ…ฉแ„แ…ณแ„‡แ…ฎแ†จ-29

์œ„์˜ ๊ทธ๋ฆผ์ฒ˜๋Ÿผ ์•„๋ฌด P๋กœ๋ถ€ํ„ฐ BFS๋กœ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๊ณ  ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š๋Š” P๋กœ๋ถ€ํ„ฐ ๋‹ค์‹œ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์† ๊ตฌํ•ด๋‚˜๊ฐ„๋‹ค.

์ด ๊ณผ์ •์„ ๊ณ„์† ๋ฐ˜๋ณตํ•˜๋ฉด์„œ ์ค‘๊ฐ„์— โ€œ๊ฑฐ๋ฆฌโ‰ง2โ€๊ฐ€ ๋‚˜์˜ค๋ฉด 0์„ ๋ฐฐ์—ด์— ์ถ”๊ฐ€์‹œํ‚ค๊ณ 

๋‹ค ๋Œ์•˜์Œ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ  โ€œ๋ชจ๋“  ๊ฑฐ๋ฆฌ < 2โ€์ด๋ฉด 1์„ ์ถ”๊ฐ€์‹œํ‚จ๋‹ค.

๊ทธ๋Ÿฐ๋ฐ ์ด๋ ‡๊ฒŒ ์„ค๊ณ„ํ•˜๊ณ  ์ฝ”๋“œ๋ฅผ ์งœ๋ ค๋‹ˆ๊นŒ ๋„ˆ๋ฌด ์–ด๋ ค์›Œ์„œ ๋ธŒ๋ฃจํŠธ ํฌ์Šค๋กœ ๋…ธ์„ ์„ ํ‹€์—ˆ๋‹ค.

์–ด์ฐจํ”ผ ์ž…๋ ฅ ์ œํ•œ์‚ฌํ•ญ๋„ ์–ผ๋งˆ ๋˜์ง€์•Š์•„์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๋Š” ๋‚˜์ง€ ์•Š์„ ๊ฒƒ ๊ฐ™์•˜๋‹ค.

๐Ÿ“ ๊ณผ์ • ์„ค๊ณ„/๊ด€๋ฆฌ

แ„‚แ…ฉแ„แ…ณแ„‡แ…ฎแ†จ-32 แ„‚แ…ฉแ„แ…ณแ„‡แ…ฎแ†จ-33 แ„‚แ…ฉแ„แ…ณแ„‡แ…ฎแ†จ-34 แ„‚แ…ฉแ„แ…ณแ„‡แ…ฎแ†จ-36

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

def matrix_slice(r1,r2,c1,c2,board):
    new_board = []
    for i in range(r1,r2+1):
        new_board.append(board[i][c1:c2+1])
    
    return new_board

def partition_check(r1,r2,c1,c2,board):
    new_board = matrix_slice(r1,r2,c1,c2,board)

    for i in range(len(new_board)):
        for j in range(len(new_board[i])):
            if new_board[i][j] == 'O':
                return False
    return True

def manhatton(r1,r2,c1,c2):
    return abs(r2-r1)+abs(c2-c1)

def solution(places):
    answer = []
    
    for k in range(5):
        temp = []

        for i in range(5):
            for j in range(5):
                if places[k][i][j] == 'P':
                    temp.append((i,j))

        flag = True
        for i in range(len(temp)):
            if flag == False:
                break
            for j in range(i,len(temp)):
                if flag == False:
                    break
                
                if temp[i] == temp[j]:
                    continue
                
                r1 = min(temp[i][0],temp[j][0])
                r2 = max(temp[i][0],temp[j][0])
                c1 = min(temp[i][1],temp[j][1])
                c2 = max(temp[i][1],temp[j][1])

                distance = manhatton(r1,r2,c1,c2)

                if distance == 2:
                    if partition_check(r1,r2,c1,c2,places[k]) == False:
                        flag = False
                if distance == 1:
                    flag = False
        
        if flag == False:
            answer.append(0)
        else:
            answer.append(1)

    return answer

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6