[ SW Expert Academy / 1861] 정사각형 방

1. 문제 이해

시작은 어느 곳이던 가능하며, 4방향으로 현재방의 +1이 있는 방으로만 움직일수있다 
어떤 수가 적힌 방에 있어야 가장 많은 갯수의 방을 이동수 있는지?

입력값:
테스트 케이스 T
한 변의 길이 N
각 방의 값 (N 줄에 걸쳐, ' '으로 나누어져있음)

유의해야 할 점:
이동할 수 있는 방의 갯수가 최대인 방이 여러개일경우 그 중 가장 작은 방을 구해야 함

출력 값:
#테스트케이스, 첫 출발 방 번호, 최대 이동가능 방 수

 

2. 문제 풀이 법

사용한 방법: DFS

처음 1에서 출발 했을 때,
1->2->3->.. 이렇게 거쳐왔다면..? 2.3에서 출발 할 필요 없다 왜냐면 겹치기 때문에!
따라서 visited를 만들어서 방문하였다.

방문(visited)하지 않은 수의 방에 대해 DFS를 실시한다

인자 : i값, x값, y값, 지나온 방의 수

 

3. 어려웠던 점

dfs를 사용하였을때 값을 가지고 나오는것을 몰랐다. 그때는 다음과 같은 방법을 쓰면 된다고 한다.

1. 어떤 인자에 함수 넣기 (내가쓴 방법)

2. global을 사용하여 변수 바꾸기

1. 어떤 인자에 함수 넣기 (내가쓴 방법)

import sys
sys.stdin = open('1861.txt')
T = int(input())
dx = [0,0,-1,1]
dy=[1,-1,0,0]
def search(i,x,y,cnt):
    for k in range(4):
        temp_x = x + dx[k]
        temp_y = y + dy[k]
        if 0<= temp_x <= N-1 and 0<= temp_y <= N-1:
            if square[temp_y][temp_x] == i+1:
                visited[i] = 1
                cnt = search(i+1,temp_x,temp_y,cnt+1)
    return cnt

for tc in range(1,T+1):
    N = int(input()) # 정사각형 한 면의 길이
    min = 1 # 방 번호
    min_cnt = 1
    square = [list(map(int,input().split()))for _ in range(N)] #사각형
    visited =[0 for _ in range(N**2+1)]

    for i in range(1,N**2+1):
        if visited[i] == 0:
            for x in range(N):
                for y in range(N):
                    if square[y][x] == i:
                        temp_cnt = search(i,x,y,1)
                        if min_cnt < temp_cnt:
                            min, min_cnt = i, temp_cnt

    print("#{} {} {}" .format(tc, min, min_cnt))

2. global을 사용하여 변수 바꾸기

T = int(input())
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def search(i,x,y):
    global temp_cnt

    for k in range(4):
        temp_x = x + dx[k]
        temp_y = y + dy[k]
        if 0<= temp_x <= N-1 and 0<= temp_y <= N-1:
            if square[temp_y][temp_x] == i+1:
                visited[i] = 1
                temp_cnt += 1
                search(i+1,temp_x,temp_y)

for tc in range(1,T+1):
    N = int(input()) # 정사각형 한 면의 길이
    min = 1 # 방 번호
    min_cnt = 1
    square = [list(map(int,input().split()))for _ in range(N)] #사각형
    visited =[0 for _ in range(N**2+1)]

    for i in range(1,N**2+1):
        if visited[i] == 0:
            for x in range(N):
                for y in range(N):
                    if square[y][x] == i:
                        temp_cnt = 1
                        search(i,x,y)
                        if min_cnt < temp_cnt:
                            min, min_cnt = i, temp_cnt

    print("#{} {} {}" .format(tc, min, min_cnt))

 

 

4. 배운 점

dfs 말고 bfs로도 풀수있다는데 풀어봐야겟다.

 

 

혹시 더 좋은 풀이나 조언이 있다면 댓글 달아주세요.