[SWEA] 1227 s/w 문제해결 기본 7일차 - 미로2

[SWEA] 1227 s/w 문제해결 기본 7일차 - 미로2

문제

단순 입력을 받고 bfs를 사용하여 갈 수 있는 길을 따라간다.

현재 방문하고 있는 위치를 visit 체크해주는 것이 가장 중요하다.

• python

  deg = [(-1, 0), (1, 0), (0, -1), (0, 1)]
  
  def is_wall(r, c):
    if r<0 or r>= 100 or c<0 or c>= 100:
        return True
    return False
  
  def bfs(start, end):
    Q.append(start)
    cnt = 0
    er, ec = end
    while Q:
        now = Q.pop(0)
        nr, nc = now
        maze[nr][nc] = 9
  
        for dr, dc in deg:
            tr, tc = nr + dr, nc + dc
            if tr == er and tc == ec:
                return 1
            if not is_wall(tr, tc) and not maze[tr][tc]:
                Q.append([tr, tc])
    return 0
  
  
  
  for tc in range(10):
    case_num = int(input())
    maze = []
    start, end = [], []
    for i in range(100):
        tmp = []
        cnt = 0
        for j in input():
            tmp.append(int(j))
            if int(j) == 2:
                start = [i, cnt]
            if int(j) == 3:
                end = [i, cnt]
            cnt += 1
        maze.append(tmp)
  
    Q = []
  
    print(f"#{tc + 1} {bfs(start, end)}")

  
  
  
  
  

• c

  #include <stdio.h>
  
  int test_num;
  int maze[100][100];
  int sr, sc;
  int er, ec;
  int rp, wp;
  int nr, nc;
  int drs[4] = { -1, 1, 0, 0 };
  int dcs[4] = { 0, 0, -1, 1 };
  int dr, dc, tr, tc;
  
  typedef struct Queue {
  	int r, c;
  }Queue;
  Queue Q[100*100];
  
  void inQue(int r, int c) {
  	Q[wp].r = r;
  	Q[wp].c = c;
  	wp++;
  }
  
  
  
  int bfs(int sr, int sc, int er, int ec) {
  	inQue(sr, sc);
  	while (rp < wp) {
  		nr = Q[rp].r;
  		nc = Q[rp].c;
  		
  
  		for (int i = 0; i < 4; i++) {
  			dr = drs[i];
  			dc = dcs[i];
  			tr = nr + dr;
  			tc = nc + dc;
  
  			if (tr == er && tc == ec) {
  				return 1;
  			}
  
  			if (maze[tr][tc] == 0) {
  				inQue(tr, tc);
  				maze[tr][tc] = 9;
  			}
  		}
  		
  
  		rp++;
  	}
  
  
  	return 0;
  }
  
  int main(void) {
  
  	for (int tc = 1; tc <= 10; tc++) {
  		scanf("%d", &test_num);
  
  		for (int r = 0; r < 100; r++) {
  			for (int c = 0; c < 100; c++) {
  				scanf("%1d", &maze[r][c]);
  				if (maze[r][c] == 2) {
  					sr = r;
  					sc = c;
  				}
  				else if (maze[r][c] == 3) {
  					er = r;
  					ec = c;
  				}
  			}
  		}
  
  		rp = wp = 0;
  		
  		
  
  		printf("#%d %d\n", tc, bfs(sr, sc, er, ec));
  	}
  
  	return 0;
  }